Шифр aes, атака "квадрат"

ШИФР AES, АТАКА “КВАДРАТ”

Мухамедзянов Э.Н.

Челябинский Государственный Университет

кафедра компьютерной безопасности и прикладной алгебры

Аннотация

В работе описан шифр AES (Rijndael) и специфичная для шифра атака «квадрат». Представлено математическое обоснование базовой атаки на 4 раунда, продолжение атаки на 5 раундов и показано как продолжить данную атаку на 6 раундов. Атака на 5 раундов реализована программно.

Шифр AES

Атака "Квадрат" является специфической для шифра AES (Rijndael). AES представляет собой блочный шифр. Длина ключа и длина блока 128 бит.

Четыре преобразования работают с промежуточным результатом, называемым Состоянием (State). Состояние можно представить в виде прямоугольного массива из 16 байт , где . Обозначим – столбец из четырех байт. Аналогично представлен ключ шифрования, где . Обозначим.

В шифре определено поле Галуа GF(2⁸), элементами которого являются байты. Байты рассматриваются как многочлены над Z₂:

, где i-й бит байта (0 или 1).

Операция сложения “”. При сложении байт соответствующие им многочлены складываются над Z₂ (1+1=0).

Операция умножения. При умножении байт соответствующие им многочлены перемножаются над Z₂ и результирующий многочлен берется по модулю простого многочлена .

В процессе работы алгоритма ключ расширяется (Key Schedule, Key Expansion). Первые 4 столбца (по 4 байта) массива являются исходным ключом (). Каждый последующий r-й набор из 4 столбцов вычисляется из предыдущего набора и используется для r-ого раунда, обозначим его . Раунд состоит из четырех различных элементарных преобразований, которые преобразуют состояние в состояние :

Замена байт – BS (Byte Substitution): применение перестановки S (также известной как S-блок, Sbox) ко всем байтам состояния независимо. для .
Сдвиг строк – SR (Shift Rows): циклический сдвиг байт по правилу .
Замешивание столбцов – MC (Mix Columns): каждый столбец состояния изменяется линейным преобразованием . Преобразование можно представить, как умножение столбца на матрицу слева:

Операция обратима: .

Добавление раундового ключа – KA (Key Addition): к текущему состоянию прибавляется раундовый ключ .

Финальный раунд не содержит операции MC. Составим 2 формулы, связывающие состояния A^r^-1 и A^r:

(1)

(2)

Атака "Квадрат"

Атака "Квадрат" основана на возможности свободного подбора атакующим некоторого набора открытых текстов для последующего их зашифрования. Эта атака для 6-раундового шифра AES (стандарт AES включает в себя 10 раундов) эффективнее, чем полный перебор по всему ключевому пространству.

Введем определения.

Λ-набор – набор из 256 входных блоков (массивов State), каждый из которых имеет байты (назовем их активными), значения которых различны для всех 256 блоков. Остальные байты (пассивные) остаются одинаковыми для всех 256 блоков из Λ-набора. Т.е. : , если байт с индексом активный и иначе.

Λ^k – Λ-набор c k активными байтами.

P_r – множество состояний в конце раунда r.

Возьмем Λ-набор и проследим его изменение в течении нескольких раундов. После элементарных преобразований BS и KA блоки Λ-набора дадут в результате другой Λ-набор с активными байтами в тех же позициях, что и у исходного. Преобразование SR сместит эти байты соответственно заданным в ней смещениям. После преобразования MC Λ-набор в общем случае необязательно останется Λ-набором (т. е. результат операции может перестать удовлетворять определению Λ-набора). Но поскольку каждый байт результата MC является линейной комбинацией (с обратимыми коэффициентами) четырех входных байт того же столбца , то столбец с единственным активным байтом на входе даст в результате на выходе столбец со всеми четырьмя активными байтами.

Рассмотрим шифрование Λ¹-набора, во всех блоках которого активен только один байт. Т.е. значение этого байта различно во всех 256 блоках, а остальные байты одинаковы. Проследим эволюцию этого байта на протяжении трех раундов. В первом раунде преобразование MC преобразует один активный байт в столбец из 4 активных байт, т.е. P₁ является Λ⁴. Во втором раунде эти 4 байта разойдутся по 4 различным столбцам в результате преобразования SR, P₂ является Λ¹⁶. Преобразование MC следующего, третьего раунда преобразует эти байты в 4 столбца, содержащие активные байты. Этот набор все еще остается Λ-набором до того момента, когда он поступает на вход MC третьего раунда.

Основное свойство Λ-набора – поразрядная сумма по модулю 2 () всех байтов, находящихся на одних и тех же местах, по всему набору равна нулю, т.е. . Действительно, поразрядная сумма неактивных (с одинаковыми значениями) байт равна нулю по определению операции “” (т.к. ), а активные байты, пробегая все 256 значений, также при поразрядном суммировании дадут нуль.

Рассмотрим теперь результат преобразования MC в третьем раунде байтов входного массива данных A в байты выходного массива данных B. Покажем, что и в этом случае поразрядная сумма всех блоков выходного набора будет равна нулю, то есть:

Таким образом, P₃ является Λ¹⁶, т.е. все данные на входе четвертого раунда сбалансированы (их полная сумма равна нулю). Этот баланс в общем случае нарушается последующим преобразованием BS. Ключ K^r также можно однозначно задать в L-представлении, которое строится следующим образом:

Зная L^r можно вычислить K^r, и обратно. Для проведения атаки потребуется множество Q₄ состоящее из 256 состояний: . Множество Q₄ можно получить из выходных данных шифра P₄ применением 2 обратных преобразований SR^-1 и MC^-1 к каждому состоянию.

Схема базовой атаки “Квадрат” на 4-раундовый AES.

Для всех

Для

Если , то

В этой схеме мы инвертируем 4-ый раунд шаг за шагом, чтобы получить сбалансированные байты P₃. При сумма будет сбалансированной.

Если предполагаемое значение байта ключа было верно, то оно будет включено в возможные варианты на место . Большая часть неверных значений байта будет отсеяно. За счет того, что поиск может производиться отдельно (параллельно) для каждого байта ключа, скорость подбора всего значения раундового ключа весьма велика. Далее по значению можно найти , а потом и – исходный ключ.

Атака "Квадрат-5"

Данная атака является продолжением базовой атаки с добавлением 5-го раунда. Зафиксируем выходные данные после 5 раунда шифрования 5 Λ-наборов P₅ и построим множество Q₅, применяя преобразований SR^-1 и MC^-1 к каждому состоянию. Любой байт P₃ на позиции

однозначно определяется 5 байтами:

Подобно базовой атаки предполагаем значение 5 байт L-представления ключа, и вычисляем байт состояния из P₃. Если сумма этих байт по одному Λ-набору не будет сбалансированной, то данная комбинация 5 байт ключа не является верной.

Введем операцию вычисления байта через , , ,, и : , где Для всех

Схема атаки для 5 раундов является продолжением базовой атаки на 5 раунд. Для вычисления одного столбца потребуется примерно операций C: – перебор всех комбинаций 5 байт ключа и – для каждой комбинации перебор всех 256 состояний Λ-набора из P₃ (для проверки сбалансированности суммы). Далее по значениям находится , и исходный ключ .

Атака "Квадрат-6"

Атака "Квадрат-6" является продолжением атаки "Квадрат-5" на 5 раундовый AES с добавлением раунда в начало. Добавим 0 раунд в начало. Основная идея заключается в том, чтобы подобрать такой набор блоков открытого текста P_-1, который на выходе нулевого раунда (P₀) давал бы Λ¹-набор. Это требует предположения о значении четырех байт ключа

, используемых преобразованием KA перед нулевым раундом.

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

для одного i давали 256 различных значений, в то время как для каждого из остальных трех значений i результат этого преобразования должен оставаться постоянным. Перед MC выполняется 3 преобразования: KA, BS и SR. Покажем, как для предполагаемых 4 байт ключа нужно подобрать столбец так, чтобы после операции MC получить заданный столбец : .

Т.к. до операции MC выполняется SR, то байты столбца нужно разнести по 4 столбцам состояния так, чтобы после SR они оказались в одном столбце. Все остальные столбцы на входе MC , где , должны состоять из пассивных байт, значения которых постоянны на всем наборе состояний. Т.к. для проведения атаки не важно на каком месте стоит активный байт в P₀, то j можно выбрать любым (). Также произвольно можно выбрать позицию активного байта в столбце .

Таким образом, получаем следующий алгоритм атаки. Имеем всего 2³² различных значений для определенных i и j. Остальные байты для всех блоков одинаковы (пассивные байты). Предположив значения четырех байт ключа 0-го раунда, подбираем набор из 256 блоков P_-1. Эти 256 блоков станут Λ¹-набором после 0-го раунда. К этому Λ¹-набору применима атака “Квадрат-5”. Подобранный с ее помощью столбец ключа последнего раунда фиксируется. Теперь подбирается новый набор из 256 блоков для того же значения и находится столбец ключа последнего раунда . Если после нескольких попыток значение не меняется, значит предположение о значении было верно. В противном случае нужно брать следующее значение . Такой алгоритм достаточно быстро приведет к полному восстановлению всех столбцов .

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

Литература:

О.С. Зензин, М.А. Иванов, Стандарт криптографической защиты – AES. Конечные поля. – М.: КУДИЦ-ОБРАЗ, 2002.
Joan Daemen, Vincent Rijmen, AES Proposal: Rijndael

http://csrc.nist.gov/encryption/aes/rijndael/Rijndael.pdf

Elisabeth Oswald, Joan Daemen, Vincent Rijmen, AES - The State of the Art of Rijndael’s Security

http://www.a-sit.at/technologieb/evaluation/aes_report_e.pdf

Программирование в среде Си для ПЭВМ ЕС/Л.М.Романовская, Т.В. Русс, С.Г. Свитковский. – М.: Финансы и статистика 1991.