Раунд

Основные операции шифра

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

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

Продолжая тему о блочном шифре победителе конкурса, проводимого Национальным институтом стандартов и технологий США (1997 2000), будем рассматривать его функционирование, работу. Агентство национальной безопасности США не являлось участником конкурса, поэтому шансы стать победителем у разработчиков были велики.

Конкурсной комиссией были предварительно отобраны 15 заявок от разных стран. Выступать могли как организации, так и частные лица. В итоге победил RIJNDAEL(Бельгия) авторы Винсент Рюмен (Vincent Rijmen) и Ион Дэмен (Joan Daemen). Структуру шифра считают классической SP-сетью.

Ранее уже приводились основные технические характеристики и повторяться не будем.

Шифрование сообщений

Разработчиками создан шедевр, впервые идеология и реализация симметричного блочного шифра стала до конца понятной, так как шифр полностью основан на элементах классической (прозрачной) алгебраической структуры (поле), с достаточно скромными для обозрения количественными характеристиками. Конечное расширенное поле (поле многочленов) характеристики 2 имеет степень расширения n=8 и число элементов (порядок поля 2⁸ = 256), отсюда обозначение поля GF(2⁸).

Выбор неприводимого многочлена поля и примитивного элемента поля = 00000011₂ = 3₁₀, также не является загадочным. Одним словом, это не DES и не отечественный ГОСТ 28147.89.
Исходные тексты подготавливаются на устройствах с клавиатурой, используя
Таблицу Символы кода ASCII

Раунды и операции шифрования АЕS

Число раундов шифра обозначается Nr и зависит от длины ключа (Nr = 10 для ключа 128 битов, Nr= 12 для ключа 192 бита и Nr = 14 для ключа 256 битов).
Цикл (один раунд) шифрования AES состоит (в изменении состояния State шифруемого сообщения) из четырех основных операций:
1. AddRoundKey S + Ki; суммирование состояния (исходного текста с ключом)
2. SubBytes ax^-1 + b; замена результатов суммирования другими байтами
3. ShiftRows; Sp(x); циклические сдвиги строк на разное число позиций
4. MixColumns A0S. перемешивание столбцов квадрата.

Покажем, как это происходит на числовом примере для текущего состояния в каждой операции, начиная с верхней (нулевой) строки. Результаты 2-й и 3-й операций не требуют числовых преобразований, но MixColumns связана с умножением 2-х матриц и определение элементов результирующей матрицы требует конкретных вычислений в поле GF(2⁸). Алгоритм выработки ключа (Kеу Schedule) формирует 32-разрядные слова, число которых равно длине блока Nb.

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

Существует анимация, поясняющая функционирование алгоритм шифра AES, весьма наглядно демонстрируются раундовые операции. Автор не ставил перед собой цели показать все детали процесса зашифрования, но даже этот упрощенный вариант (на уровне байтов), что почти совпадает с элементами поля GF(2⁸), удачно демонстрирует работу шифра AES. Детальное изложение для уяснения математических основ работы с элементами поля и конкретная реализация в различных представлениях элементов поля здесь.

Операция AddRoundKey для i-го раунда

Суммирование столбцов State с раундовым ключом (Add Round Key).

Раундовый ключ, предварительно вычисленный и выбранный, представляется в форме (квадрат) State (Key). Суммирование выполняется для одноименных столбцов. Пара столбцов State (Data) и State (Key) операцией XOR поразрядно складывается.

Таким образом, преобразование AddRoundKey состоит из суммирования матрицы S блока (квадрата 44) сообщения в M4(GF(2⁸)) с частичным Ki ключом i-го раунда (также с квадратом 44 ). Результат суммирования обозначается SiA, т е. состояние после i-го AddRoundKey M4(GF (2⁸)) M4(GF (2⁸)), S SiA = S + Ki.
В начальном раунде (r = 0) выполняется только Add RoundKey суммирование по mod2 (XOR) байтов блока данных и блока ключа. Результат этого раунда используется как исходное (State) состояние для первого раунда (r=1) и представляется в формате квадрат.
Шифрование сообщений AES

Пример 1. Сообщение (исходный текст = ИТ) в 16-ричном представлении
имеет вид 32 43 f6 a8 88 5a 30 8d 31 31 98 a2 e0 37 07 34,
а ключ шифра 2b 7e 15 16 28 ae d2 a6 ab f7 15 88 09 0f 4f 3c.
Операция AddRoundKey S + Ki для всех 16 байтов квадрата State
Предварительный раунд зашифрования подготавливает сумму ИТ с ключом.

Их Сумма, представленная байтами в формате квадрат при Nb = Nk = 4 и Nr = 10 имеет вид:


Рисунок Результат предварительного раунда (до первого)

Ключ и исходный текст (это может быть и звук и картинка и др.) представлены в 16-ричном виде. Это не самое удобное представление, поэтому преобразуем его к двоичным векторам и выполняем сложение по модулю 2.



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

Операция SubByte для i-го раунда

Замена байтов (Sub Bytes ( ) )

Первый раунд. Операция AddRoundKey уже выполнена. Все байты суммарного квадрата (исходного состояния обозначим их точками (х, y) на некоторой плоскости) преобразуются функцией S (x, y) в новые значения табличка "Замена байтов".

Заменяем угловой (левый верхний) байт State = Сумма, (равный 19), на байт d4 из таблицы замен S-блока и следующий (3D) на 27 (они выделены заливкой). Так преобразуются все 16 байтов квадрата "Сумма".

Так для первого байта {19} = {x, y}, x = 1, y = 9, S(19) = d4. Все такие значения также представляются квадратом с замещениями.

Функция S (x, y) табулирована, т. е. задана таблицей с двумя входами строка (х) и столбец (у). Поскольку все многообразие байтов исчерпывается числом 256, то таблица имеет размер 1616 = 256, а ее строки и столбцы пронумерованы x, y = 0(1)15 цифрами 16-ричной системы счисления. Вид таблицы S (x, y) приведен ниже.



Покажем, как получены значения этой таблицы S (x, y). Вначале каждый байт исходного состояния {x, y} преобразуется в инвертированный {x, y}^-1, в мультипликативный обратный в поле GF(2⁸). Затем байт умножается на матрицу А. Нулевой байт переходит в себя {0, 0}^-1 = {0, 0}.

Каждая строка матрицы аффинного преобразования А содержит лишь пять единиц.

Затем к инвертированному (обращенному) байту применяют аффинное преобразование, которое в векторно-матричной форме записывается так



Аффинная матрица

Запись векторов сверху (младший разряд) вниз. Вектор сдвига c = {63}₁₆, что в таблице S (x, y) отражено для байта {00}. Каждый байт исходного состояния подвергается такому преобразованию, и их значения вписаны в квадратную таблицу S (x, y).

Скалярное представление аффинного преобразования имеет следующий вид (общий вид i -го элемента результата):


где ; , ^' соответственно исходное и преобразованное значение i-го разряда байтов, i = 0(1)7.

Выражение для ^' содержит 6 слагаемых, так как каждая строка циклической матрицы аффинного преобразования имеет лишь 5 ненулевых элементов; шестое слагаемое берется из вектора сдвига ci.

Для ускорения вычислений используется квадратная таблица фиксированных значений (S (x, y) блок). Значение b =63 16 ричное число принадлежит GF(2⁸) и матрица а имеет вид, показанный ранее. В сущности, операция реализует подстановку (замену) байт из S квадрата 1616.

Преобразование SubByte состоит в применении к каждому элементу матрицы S элементарного преобразования s. Результат этой операции обозначается SiSu, т. е. это состояние блока текста после операции SubByte i-го раунда. Не путать буквы S и s (большую и малую).

В сущности, здесь выполняется аффинное преобразование с постоянным вектором сдвига, обозначаемым символом b
M4 (GF(2⁸)) M4 (GF(2⁸)).

Запись векторов сверху (младший разряд) вниз. Вектор сдвига c = {63}₁₆, что в таблице S (x, y) отражено для байта {00}. Каждый байт исходного текста (состояния) подвергается такому преобразованию, и их значения вписаны в таблицу S (x, y).

Пример 2. Первый байт исходного состояния первого раунда равен {19}. Мультипликативный обратный для него (см. Табл. П1) равен 3f = {19}^-1= 0011 1111₂ =¹¹³. Это значение легко находится по таблице элементов поля GF(2⁸). При отсутствии таблицы элементов поля можно выполнить и непосредственные вычисления.

Пусть байт {x, y} = 09 = ¹⁹⁹ и {09} ^-1 = 4f, тогда
b0 = (1+0+1)mod2 = 0, b4 = (1+1+0)mod2 = 0,
b1 = (1+0+1)mod2 = 0, b5 = (0+1+1)mod2 = 0,
b2 = (1+0+0)mod2 = 1, b6 = (0+1+1)mod2 = 0,
b3 = (1+1+0)mod2 = 0, b7 = (0+1+0)mod2 = 1.
Результирующий вектор ( 0, 1, 2, 3, 4, 5, 6, 7) =1000 0100₂ = 84.

Следовательно, байт 4f S-блоком преобразуется в байт 84, что можно увидеть в таблице замен S (x, y) = S (4, f) = 84. Этот результата лежит на пересечении строки с номером 4 и столбца с номером f. Геометрическое представление замены байтов (SubBytes) изображено на рисунке 4, где s нелинейное преобразование, определяемое соотношениями:
GF(2⁸) GF(2⁸),

Операция ShiftRows для i-го раунда

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

Выбор величин сдвигов подчинен следующим условиям:
Каждая строка должна иметь индивидуальное смещение элементов;
Реализация операции должна быть простой;

Совокупность сдвигов наилучшим образом должна препятствовать проведению атак:

А) атак, использующих сокращенные дифференциалы
В) атак типа Square.


Рисунок 5 Состояние после сдвига строк

ShiftRows преобразование перемещения байтов строки в матрице состояния S, которое циклически сдвигает строки матрицы состояния на различные по величине смещения. Результат операции обозначается SiSh, т. е. это состояние после операции ShiftRows
i-го раунда. Такие перемещения могут быть описаны Р(х) перестановкой байт из квадрата S, которая имеет вид:


Из всех вариантов сдвигов, обеспечивающих наилучшее противостояние атакам, был выбран самый простой циклический сдвиг и c0 = 0.

Геометрическое представление преобразования замены байтов изображено на рисунке 4, где приведены квадраты числового примера для первого раунда.

Сдвиг строк в массиве State выполняется влево. Строка с номером нуль остается неподвижной (не сдвигается). Остальные строки RIJNDAEL сдвигаются на число байтов c1, c2, c3, указанное в квадрате на рисунке 5), в зависимости от числа Nb байтов в блоке данных. Строка 1 сдвигается на c1 байтов, строка 2 на c2 байтов и строка 3 на с3 байтов.

В стандарте AES величина Nb = 128 постоянная, поэтому всегда c1 = 1, c2 = 2 и c3 = 3.

Таблица Величины сдвигов

Операция MixColumns для i-го раунда

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

• Обратимость получаемого результата.
• Линейность в поле GF(2⁸); выполнение этого требования создает условия для применения алгоритма прямого расшифрования.
• Достаточно сильное рассеивание данных.
• Высокую скорость реализации на 8-разрядных процессорах; единообразие обработки любых блоков данных, т. е. симметричность.
• Простой вид для описания и реализации.

Все названные требования удовлетворены в стандарте АES. Из возможных линейных преобразований 4 bytes 4 bytes выбрана операция умножения многочленов (элементов поля) по модулю (x) = x⁴ + 1. Выбор коэффициентов сомножителей обусловлен требованиями 1, 3 и 4. Коэффициенты {00}, {01}, {02}, {03}, соответствуют: {00} отсутствию преобразования; {01} не требуется умножения; {02} умножение при использовании функции x time ( ) и {03} при использовании x time и последующего сложения по mod2 промежуточных результатов.

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

Сущность преобразования Mix Columns ( ) состоит в следующем. Столбцы State
S = < S0c, S1c, S2c, S3c>, с = 0(1)3, после сдвига строк рассматриваются как элементы поля GF(2⁸) и умножаются по mod(x⁴ + 1) на фиксированный многочлен g(x):
g(x) = {03}x³+{0,1}x²+{01}x+{02}.


где с номер столбца State, c = 0(1)3.

где А циркулянтная матрица, т. е. линейное инвертируемое (обратимое) отображение на GF (2⁸), А принадлежит M8(GF (2⁸)),
обозначает умножение матрицы из GF (2⁸) и вектора
х -1 = {b0 b1b7 }b, который рассматривается как элемент над полем GF(2) векторного пространства, эквивалентный транспонированному в вектор {b0 b1b7 }b.

Развернем это выражение в скалярную форму
S0C = ({02} S0C) ({03} S1C) S2C S3C;
S1C = S0C ({02} S1C) ({03} S2C) S3C;
S2C = S0C S1C ({02}S2C) ({03} S3C);
S3C = ({03} S0C) S1C S2C ({02} S3C).
В результате выполнения указанных действий байты вектора
SC = <S0c, S1c, S2c, S3c> будут заменены байтами S0C, S1C, S2C, S3C.

MixColumns преобразование состоит из умножения двух матриц. Матрицы S промежуточного состояния текста и фиксированной матрицы A0 обе из введенного ранее множества M4 (GF (2⁸)). Результат операции обозначается символом SiM, это по существу состояние S после операции MixColumns i-го раунда.

M4 (GF (2⁸)) M4 (GF (2⁸)),
S Si, М = АS,
где матрицы А и А^-1 (циркулянтные матрицы) определяются как:

.
Операция MixColumns произведение специальной цикловой А0 матрицы на матрицу State, по правилу строка на столбец

.
Два пустых столбца в результирующей матрице оставлены для самостоятельного заполнения.
Начинаем с левого углового элемента нулевой строки квадрата. Его значение определяется суммой произведений пар элементов: {02}D4{03}BF {01}5D {01}30. Элементы обеих матриц это элементы поля GF(2⁸) с одной стороны и информационные байты в 16-ричном представлении с другой. Умножение элементов в поле удобно выполнять в степенном представлении примитивного элемента.

Пользуясь таблицей поля, выполним замену 16-ричного представления на степенное для левой цикловой матрицы элементы {01} = a⁰, {02} = a²⁵, {03} = a¹. Для правой матрицы в произведении получим


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

1-й элемент нулевой строки определяется в виде:

{02}D4 {03}BF {01}5D {01}30 = a²⁵а⁶⁵ a¹а¹⁵⁷ a⁰а¹³⁶ a⁰а¹⁰¹ = а⁹⁰ a¹⁵⁸а¹³⁶а¹⁰¹,

2-й элемент нулевой строки определяется аналогичным соотношением (поменялся столбец)

{02}Е0{03}B4 {01}52 {01}АЕ = a²⁵а⁶⁸ a¹а²⁵¹ a⁰а²⁵³ a⁰а¹²³ = а⁹³ a²⁵² а²⁵³а¹²³,

3-й элемент нулевой строки определяется аналогичным соотношением поменялся столбец

{02}B8{03}41 {01}11 {01}F1 = a²⁵а⁵⁹ a¹а¹⁴³ a⁰а⁴ a⁰а⁷⁴ = а⁸⁴ a¹⁴⁴ а⁴ а⁷⁴,

4-й элемент нулевой строки определяется аналогичным соотношением поменялся столбец

{02}1Е{03}27 {01}98 {01}Е5 = a²⁵а²⁸ a¹а¹⁰⁶ a⁰а⁸⁹ a⁰а³² = а⁵³a¹⁰⁷ а⁸⁹а³².

Показатели степеней просто суммируются при перемножениях как логарифмы. Суммирование слагаемых удобно выполнить возвратом к 16-ричному, а от него к двоичному представлению. Опять воспользуемся таблицей элементов поля GF(2⁸).



Перейдем к вычислению элементов 1-й строки матрицы (изменяется номер строки циклической матрицы) Элементы в парах произведений изменяются относительно 0-й строки.

1-й элемент 1-й строки матрицы перемешанных столбцов определяется соотношением.


Перейдем к вычислению элементов 2-й строки матрицы (изменяется номер строки циклической матрицы). Элементы в парах произведений изменяются относительно 1-й строки.

1-й элемент 2-й строки матрицы перемешанных столбцов определяется соотношением



Перейдем к вычислению элементов 3-й строки матрицы (изменяется номер строки циклической матрицы) Элементы в парах произведений изменяются относительно 2-й строки.

После подробного изложения с деталями отдельных преобразований, с элементами конечного не отвлеченного (как во множестве публикаций, не исключая и Хабровских) алгебраического поля, а (конкретного), в рамках которого реализуется RIJNDAEL, AES-128 и (выполнения операций стандарта AES-128), можно перейти к рассмотрению возможных атак на шифр. Пока ограничимся одной атакой, по нашему мнению, наиболее доступной для понимания и прозрачно построенной (хотя, возможно, не всем читателям) Хабра.

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

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

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

1. Атака на ключ шифра AES

Сначала, описывается атака на AES в простом случае, и после этого становится видно, как можно обобщить такую атаку. Цель рассматриваемой атаки состоит в том, чтобы восстановить ключ K(Nr) шифра. Как только определяется частичный (раундовый) ключ K(Nr), становится просто получить ключ K.

1.1 Принцип атаки

Предполагается, что есть возможность изменять путем внесения ошибки "" в отдельный байт матрицы S состояния (один из 16) после операции ShiftRows (Nr 1), т. е. предпоследнего раунда, и известен индекс (#клетки) искаженного байта (элемента) состояния. Эта последняя гипотеза может быть опущена, она введена для того, чтобы более доступно объяснить механизм атаки. Новое значение элемента состояния предполагается неизвестным.

Ошибка "" распространяется на не более чем четыре байта состояния выхода процесса. Для всех 4-х изменяемых элементов состояния выхода, находится множество значений (набор) векторов возможной ошибки " " п. 1.4. Кроме того, появляется возможность пересекать множества возможных значений "" (определение 1) для этих четырех элементов. При пересечении таких множеств получается меньший набор, и таким образом, сокращается количество требуемых зашифрованных текстов для полного анализа.

Наконец, для каждой ошибки, мы выводим некоторые возможные искаженные значения четырех элементов предшествующего раундового ключа. Формируя другие зашифрованные тексты, мы находим четыре байта раундового ключа К(10). Эта атака остается успешной даже с большим количеством общих предположений о местоположении ошибки. Таких как отсутствие сведений о местоположении ошибки перед 9-м MixColumns() преобразованием. Разность матрицы шифрованного текста с искажениями и без них выявит искажения и их положение (в примере это позиции 0,7,10,13).

Предполагается также, что ошибки " ", вводимые в раунде 8 (до 8-го MixColumns() преобразования), могли бы быть полезными для анализа. Но при этом возрастает количество требуемых зашифрованных текстов для более полного анализа. Для рассматриваемого числового примера, необходимо около десяти зашифрованных текстов, чтобы получить четыре байта раундового ключа К(10), в условиях, когда не рассматривается гипотеза относительно местоположений ошибки.

1.2 Числовой пример воздействия ошибки на сообщение

Здесь используется тот же самый пример, который приводится в Приложении названной работы. Рассматриваются предпоследний и последний раунды процесса шифрования (байтовое представление данных имеет вид):

Вход = 32 43 F6 A8 88 5A 30 8D 31 31 98 A2 E0 37 07 34;
Ключ шифра = 2B 7E 15 16 28 AE D2 A6 AB F7 15 88 09 CF 4F 3C;
Выход = 39 25 84 1D 02 DC 09 FB DC 11 85 97 19 6A 0B 32;
Ошибка " " = 1Е 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00.

Следующая диаграмма показывает значения, содержащиеся в массивах состояний, в соответствии с длиной шифрблока и длиной ключа шифра по 16 байтов каждый (то есть, Nb = 4 и Nk = 4).

Распространение ошибки показывается жирным шрифтом и в шестнадцатеричном представлении. Ниже представлены квадраты состояния State в разных ситуациях


Ошибка " " = 1E, введенная в 0-й байт состояния 9-го раунда, приводит к изменениям в четырех байтах конечного состояния. Примеры вычислений для угловых клеток главной диагонали квадрата состояния:

в левую верхнюю (угловую) клетку квадрата State 9-го раунда вводится ошибка " " = 1Е

87 1Е = 1000 0111 0001 1110 = 1001 1001 = 99
нижний правый угол State 9-го раунда после MixColum9 суммируется с байтом ключа К(9):

BC 6E = 1011 1100 0110 1110 = 1101 0010 = d2.
вычисления значений результирующей ошибки.

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

Например, в 16-ричном виде находим значения ошибок:
Таблица 7 вычисление значений ошибок

Получили в итоге разностные ошибки $inline$ _0=E7, _1=51, _2=47, _3=99$inline$. Дадим пример вычисления последнего байта ошибки:

62 FB = 01100010 11111011 = 1001 1001 = 99.
Положения измененных ошибкой байтов состояния
$inline$ _0=E7, _1=51, _2=47, _3=99$inline$.указывают на индексы для элементов раундового ключа (последнего раунда), как К[0], K[7], K[10], K[13]. Здесь 0, 7, 10, 13 номера клеток матрицы состояния, а матрица Ао это матрица преобразования перемешивания столбцов процесса зашифрования, первый столбец которой имеет вид: 02, 01, 01, 03.

Как введенная ошибка действует на конечном заключительном состоянии

.

Анализ информации, получаемой при введении ошибки

Единственной операцией, которая может содержать информацию относительно ключа K(Nr) является последнее SubBytes( ) преобразование. Следовательно, мы имеем четыре уравнения, где x0, x1, x2, x3, являются неизвестными переменными.

Мы хотим получить решения следующих четырех уравнений:




Байты $inline$ _0, _1, _2, _3$inline$, измененные ошибкой, содержат информацию о неизвестном ключе, сформировавшем эти байты.

Все такие уравнения можно обобщить в единственном уравнении
s(x +c) + s(x) =, (1)
где постоянная величина с = 01, 02 или 03 и именно это уравнение будем далее решать и анализировать.

Определение 1. Множество решений уравнения (1) для ошибок обозначим символом B(c) и определим выражением:
B(c)=S(c)={ GF [2⁸]: x GF [2⁸],s(x +c) + s(x) =}, |B(c)| =127.

Это индивидуальная область ошибок, соответствующая конкретной ошибке . Для других области для ошибок будут другими.

Определение 2. Рассмотрим линейное преобразование над полем GF (2):
: GF [2⁸] GF [2⁸];
xx² + x.

Образ отображения Im() GF (2)-векторного пространства, т.е. множество элементов
(x² + x) из GF [2⁸] обозначим Е1 = Im() и его размерность dimGF(2)(E1) = 7. Если Е1, то существуют два различных решения x1, x2 GF [2⁸] уравнения x²+x=, и решения удовлетворяют соотношению x2 = x1 + 1 и x2x1 = (modd x,(2⁸-1) ) по теореме Виеты.
Переменная это свободный член квадратного уравнения

Проиллюстрируем примером рассмотренное линейное преобразование.
Пример Задано поле GF [2⁸], над его элементами выполняется преобразование xx² + x.

Таблица 8 начальный фрагмент поля GF [2⁸] и результаты преобразования элементов.


В таблице 8 показано как преобразование изменяет пары, рядом стоящих в упорядоченном по десятичным значениям элементов списке, в один и тот же элемент поля. Из этого следует, что результат преобразования (образ) в два раза меньше прообраза (поле как бы сжимается в 2 раза). Этот принцип сжатия размерности множеств положен в основание предлагаемой атаки.


Предложение 2. Следующее утверждение справедливо для 1, 2 GF [2⁸] {0}:

2. Обобщение и реализация

Первым делом при помощи специального программного приложения формируются 20-ть шифртекстов с ошибкой. Для этого вводятся в модель (программу) исходный текст, ключ, ошибка и задается номер позиции, в которой ошибка помещается. Нажатием кнопки Пуск программа реализует алгоритм и выведет результаты 2-х последних раундов шифрования в развернутом виде для текста с ошибкой, текста без ошибки и разность между ними. После этого сохраняется шифртекст без ошибки и с ошибкой. Циклически изменяется значение ошибки и нажатием кнопки Пуск получают следующий шифртекст с ошибкой. На одном значении столбца формировалось по 5 шифртекстов с ошибкой.
Для реализации атаки необходимо при помощи программы открыть файл с шифртекстом без ошибки и шифртекстом с ошибкой (данные в файле представляются в 16-ричном виде), шифртексты и разность между ними отображаются в виде квадратного массива байтов (State). Нажатием кнопки Искать ключ запускается процедура поиска возможных байтов ключа. Текущее состояние процессов отображается в текстовом окне. После этого открывается шифртекст с другой ошибкой, и процедура повторяется. При получении байта ключа 10-го раунда он также отображается в соответствующем квадратном массиве байтов. При прогонке всех 20 сформированных на предыдущем этапе шифртекстов с ошибкой велика вероятность получения значений всех байтов ключа 10 раунда (иначе нужны ещё шифртексты с ошибками). После этого восстановить ключ шифрования по алгоритму Восстановление ключа шифра с использованием последнего подключа приведенному здесь.


Рисунок 11 Программный продукт построения шифртекста с ошибкой

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


Рисунок 12 Программная реализация атаки

Пример работы программного продукта
Исходный текст 3243f6a8885a308d313198a2e0370734
Ключ 2b7e151628aed2a6abf7158809cf4f3c
Ошибка 1 1e000000000000000000000000000000
Шифртекст с ошибкой 1 de25841d02dc0962dc11c297193b0b32
Возможные байты ключа




Рисунок 13 Пример работы программы

Ключ 10 раунда d014f9a8c9ee2589e13f0cc8b6630ca6 ключ полностью восстановлен
Восстановленный ключ 2b7e151628aed2a6abf7158809cf4f3c, как и ожидалось он совпадает с заданным в сеансе шифрования ключом.

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

В этом пункте, предполагается, что ошибка содержится в байте состояния, между последними двумя выполнениями операции MixColumns. Это тот же самый случай, когда предварительно за исключением того, что ошибка может быть заключена между байтов от 1 до 16. Ошибка при этом размножается операцией MixColumns и распространяется уже на 4 байта состояния.

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

2.2. Аппаратное устройство

Предположим, что имеется возможность физически воздействовать на аппаратное устройство AES. Сначала вычислим шифры для более чем десяти случайных открытых текстов при помощи AES устройства. Затем изменяем примером проект, вырезая строки и подключая их к земле (или Vcc) temporaly между двумя байтами в течение раунда, расположенного в двух раундах перед завершением. В конце концов, мы имеем байт в раунде Nк -2, всегда заменяемый 00 (или FF).

Вычисляем другой раз то же самое сообщение с воздействующим устройством. Со случайными открытыми текстами, дефектный байт подобен случайной ошибке. Эта одиночная ошибка переходит в четыре ошибки в раунде Nк -1 и в шестнадцать ошибок в раунде Nк. При этом может быть получена матрица отклонений (дифференциальная), с помощью которой возможно, анализируя ошибку, найти последний раундовый ключ.

Литература
[1] FIPS PUB 197: Advanced Encryption Standard, csrc.nist.gov/publications/fips/fips197/fips-197.pdf
[2] Boneh, DeMillo, and Lipton, On the Importance of Checking Cryptographic Protocols for Faults, Lecture Notes in Computer Science, Advances in Cryptology, proceedings of EU-ROCRYPT97, pp. 37-51, 1997.
[3] E. Biham & A.Shamir, Differential Fault Analysis of Secret Key Cryptosystems, CS 0910, Proceedings of Crypto97.
[4] Ross J. Anderson, Markus G. Kuhn: Tamper Resistance a Cautionary Note, The Second USENIX Workshop on Electronic Commerce Proceedings, Oakland, California, November 18-21, 1996, pp 1-11, ISBN 1-880446-83-9.