AES (стандарт шифрования)

S-box

Sbox = array{
        0x63, 0x7c, 0x77, 0x7b, 0xf2, 0x6b, 0x6f, 0xc5, 0x30, 0x01, 0x67, 0x2b, 0xfe, 0xd7, 0xab, 0x76, 
        0xca, 0x82, 0xc9, 0x7d, 0xfa, 0x59, 0x47, 0xf0, 0xad, 0xd4, 0xa2, 0xaf, 0x9c, 0xa4, 0x72, 0xc0, 
        0xb7, 0xfd, 0x93, 0x26, 0x36, 0x3f, 0xf7, 0xcc, 0x34, 0xa5, 0xe5, 0xf1, 0x71, 0xd8, 0x31, 0x15, 
        0x04, 0xc7, 0x23, 0xc3, 0x18, 0x96, 0x05, 0x9a, 0x07, 0x12, 0x80, 0xe2, 0xeb, 0x27, 0xb2, 0x75, 
        0x09, 0x83, 0x2c, 0x1a, 0x1b, 0x6e, 0x5a, 0xa0, 0x52, 0x3b, 0xd6, 0xb3, 0x29, 0xe3, 0x2f, 0x84, 
        0x53, 0xd1, 0x00, 0xed, 0x20, 0xfc, 0xb1, 0x5b, 0x6a, 0xcb, 0xbe, 0x39, 0x4a, 0x4c, 0x58, 0xcf, 
        0xd0, 0xef, 0xaa, 0xfb, 0x43, 0x4d, 0x33, 0x85, 0x45, 0xf9, 0x02, 0x7f, 0x50, 0x3c, 0x9f, 0xa8, 
        0x51, 0xa3, 0x40, 0x8f, 0x92, 0x9d, 0x38, 0xf5, 0xbc, 0xb6, 0xda, 0x21, 0x10, 0xff, 0xf3, 0xd2, 
        0xcd, 0x0c, 0x13, 0xec, 0x5f, 0x97, 0x44, 0x17, 0xc4, 0xa7, 0x7e, 0x3d, 0x64, 0x5d, 0x19, 0x73, 
        0x60, 0x81, 0x4f, 0xdc, 0x22, 0x2a, 0x90, 0x88, 0x46, 0xee, 0xb8, 0x14, 0xde, 0x5e, 0x0b, 0xdb, 
        0xe0, 0x32, 0x3a, 0x0a, 0x49, 0x06, 0x24, 0x5c, 0xc2, 0xd3, 0xac, 0x62, 0x91, 0x95, 0xe4, 0x79, 
        0xe7, 0xc8, 0x37, 0x6d, 0x8d, 0xd5, 0x4e, 0xa9, 0x6c, 0x56, 0xf4, 0xea, 0x65, 0x7a, 0xae, 0x08, 
        0xba, 0x78, 0x25, 0x2e, 0x1c, 0xa6, 0xb4, 0xc6, 0xe8, 0xdd, 0x74, 0x1f, 0x4b, 0xbd, 0x8b, 0x8a, 
        0x70, 0x3e, 0xb5, 0x66, 0x48, 0x03, 0xf6, 0x0e, 0x61, 0x35, 0x57, 0xb9, 0x86, 0xc1, 0x1d, 0x9e, 
        0xe1, 0xf8, 0x98, 0x11, 0x69, 0xd9, 0x8e, 0x94, 0x9b, 0x1e, 0x87, 0xe9, 0xce, 0x55, 0x28, 0xdf, 
        0x8c, 0xa1, 0x89, 0x0d, 0xbf, 0xe6, 0x42, 0x68, 0x41, 0x99, 0x2d, 0x0f, 0xb0, 0x54, 0xbb, 0x16
    };

Обратный S-box для процедуры InvSubBytes

InvSbox = array{
        0x52, 0x09, 0x6a, 0xd5, 0x30, 0x36, 0xa5, 0x38, 0xbf, 0x40, 0xa3, 0x9e, 0x81, 0xf3, 0xd7, 0xfb,
        0x7c, 0xe3, 0x39, 0x82, 0x9b, 0x2f, 0xff, 0x87, 0x34, 0x8e, 0x43, 0x44, 0xc4, 0xde, 0xe9, 0xcb,
        0x54, 0x7b, 0x94, 0x32, 0xa6, 0xc2, 0x23, 0x3d, 0xee, 0x4c, 0x95, 0x0b, 0x42, 0xfa, 0xc3, 0x4e,
        0x08, 0x2e, 0xa1, 0x66, 0x28, 0xd9, 0x24, 0xb2, 0x76, 0x5b, 0xa2, 0x49, 0x6d, 0x8b, 0xd1, 0x25,
        0x72, 0xf8, 0xf6, 0x64, 0x86, 0x68, 0x98, 0x16, 0xd4, 0xa4, 0x5c, 0xcc, 0x5d, 0x65, 0xb6, 0x92,
        0x6c, 0x70, 0x48, 0x50, 0xfd, 0xed, 0xb9, 0xda, 0x5e, 0x15, 0x46, 0x57, 0xa7, 0x8d, 0x9d, 0x84,
        0x90, 0xd8, 0xab, 0x00, 0x8c, 0xbc, 0xd3, 0x0a, 0xf7, 0xe4, 0x58, 0x05, 0xb8, 0xb3, 0x45, 0x06,
        0xd0, 0x2c, 0x1e, 0x8f, 0xca, 0x3f, 0x0f, 0x02, 0xc1, 0xaf, 0xbd, 0x03, 0x01, 0x13, 0x8a, 0x6b,
        0x3a, 0x91, 0x11, 0x41, 0x4f, 0x67, 0xdc, 0xea, 0x97, 0xf2, 0xcf, 0xce, 0xf0, 0xb4, 0xe6, 0x73,
        0x96, 0xac, 0x74, 0x22, 0xe7, 0xad, 0x35, 0x85, 0xe2, 0xf9, 0x37, 0xe8, 0x1c, 0x75, 0xdf, 0x6e,
        0x47, 0xf1, 0x1a, 0x71, 0x1d, 0x29, 0xc5, 0x89, 0x6f, 0xb7, 0x62, 0x0e, 0xaa, 0x18, 0xbe, 0x1b,
        0xfc, 0x56, 0x3e, 0x4b, 0xc6, 0xd2, 0x79, 0x20, 0x9a, 0xdb, 0xc0, 0xfe, 0x78, 0xcd, 0x5a, 0xf4,
        0x1f, 0xdd, 0xa8, 0x33, 0x88, 0x07, 0xc7, 0x31, 0xb1, 0x12, 0x10, 0x59, 0x27, 0x80, 0xec, 0x5f,
        0x60, 0x51, 0x7f, 0xa9, 0x19, 0xb5, 0x4a, 0x0d, 0x2d, 0xe5, 0x7a, 0x9f, 0x93, 0xc9, 0x9c, 0xef,
        0xa0, 0xe0, 0x3b, 0x4d, 0xae, 0x2a, 0xf5, 0xb0, 0xc8, 0xeb, 0xbb, 0x3c, 0x83, 0x53, 0x99, 0x61,
        0x17, 0x2b, 0x04, 0x7e, 0xba, 0x77, 0xd6, 0x26, 0xe1, 0x69, 0x14, 0x63, 0x55, 0x21, 0x0c, 0x7d
        };

Rcon[]

Rcon = array{
        array{0x00, 0x00, 0x00, 0x00},
        array{0x01, 0x00, 0x00, 0x00},
        array{0x02, 0x00, 0x00, 0x00},
        array{0x04, 0x00, 0x00, 0x00},
        array{0x08, 0x00, 0x00, 0x00},
        array{0x10, 0x00, 0x00, 0x00},
        array{0x20, 0x00, 0x00, 0x00},
        array{0x40, 0x00, 0x00, 0x00},
        array{0x80, 0x00, 0x00, 0x00},
        array{0x1b, 0x00, 0x00, 0x00},
        array{0x36, 0x00, 0x00, 0x00}
    };

AES является стандартом, основанным на алгоритме Rijndael. Для AES длина input (блока входных данных) и State (состояния) постоянна и равна 128 бит, а длина шифроключа K составляет 128, 192, или 256 бит. При этом исходный алгоритм Rijndael допускает длину ключа и размер блока от 128 до 256 бит с шагом в 32 бита. Для обозначения выбранных длин input, State и Cipher Key в 32-битных словах используется нотация Nb = 4 для input и State, Nk = 4, 6, 8 для Cipher Key соответственно для разных длин ключей.

Вначале зашифровывания input копируется в массив State по правилу ${\displaystyle \mathrm {state} [r,c]=\mathrm {input} [r+4c]}$, для ${\displaystyle 0\leq r<4}$ и ${\displaystyle 0\leq c<Nb}$. После этого к State применяется процедура AddRoundKey(), и затем State проходит через процедуру трансформации (раунд) 10, 12, или 14 раз (в зависимости от длины ключа), при этом надо учесть, что последний раунд несколько отличается от предыдущих. В итоге, после завершения последнего раунда трансформации, State копируется в output по правилу ${\displaystyle \mathrm {output} [r+4c]=\mathrm {state} [r,c]}$, для ${\displaystyle 0\leq r<4}$ и ${\displaystyle 0\leq c<Nb}$.

Отдельные трансформации SubBytes(), ShiftRows(), MixColumns() и AddRoundKey() — обрабатывают State. Массив w[] — содержит key schedule.

Cipher(byte in[4*Nb], byte out[4*Nb], word w[Nb*(Nr+1)])
begin
    byte state[4,Nb]
    
    state = in

    AddRoundKey(state, w[0, Nb-1])

    for round = 1 step 1 to Nr-1
        SubBytes(state)
        ShiftRows(state)
        MixColumns(state)
        AddRoundKey(state, w[round*Nb, (round+1)*Nb-1])
    end for

    SubBytes(state)
    ShiftRows(state)
    AddRoundKey(state, w[Nr*Nb, (Nr+1)*Nb-1])

    out = state
end

Рис1. Псевдокод для Cipher

В процедуре SubBytes, каждый байт в state заменяется соответствующим элементом в фиксированной 8-битной таблице поиска, S; b_ij = S(a_ij).

Процедура SubBytes() обрабатывает каждый байт состояния, независимо производя нелинейную замену байтов, используя таблицу замен (S-box). Такая операция обеспечивает нелинейность алгоритма шифрования. Построение S-box состоит из двух шагов. Во-первых, производится взятие обратного числа в поле Галуа ${\displaystyle GF\left({2^{8}}\right)}$. Во-вторых, к каждому байту b, из которых состоит S-box, применяется следующая операция:

${\displaystyle b'_{i}=b_{i}\oplus b_{\left({i+4}\right){\bmod {8}}}\oplus b_{\left({i+5}\right){\bmod {8}}}\oplus b_{\left({i+6}\right){\bmod {8}}}\oplus b_{\left({i+7}\right){\bmod {8}}}\oplus c_{i}}$

где ${\displaystyle 0\leq i<8}$, и где ${\displaystyle b_{i}}$ есть i-ый бит b, а ${\displaystyle c_{i}}$ — i-ый бит константы ${\displaystyle c=63_{16}=99_{10}=01100011_{2}}$. Таким образом обеспечивается защита от атак, основанных на простых алгебраических свойствах.

${\displaystyle {\begin{Vmatrix}b_{0}^{'}\\b_{1}^{'}\\b_{2}^{'}\\b_{3}^{'}\\b_{4}^{'}\\b_{5}^{'}\\b_{6}^{'}\\b_{7}^{'}\end{Vmatrix}}={\begin{Vmatrix}1&0&0&0&1&1&1&1\\1&1&0&0&0&1&1&1\\1&1&1&0&0&0&1&1\\1&1&1&1&0&0&0&1\\1&1&1&1&1&0&0&0\\0&1&1&1&1&1&0&0\\0&0&1&1&1&1&1&0\\0&0&0&1&1&1&1&1\end{Vmatrix}}*{\begin{Vmatrix}b_{0}\\b_{1}\\b_{2}\\b_{3}\\b_{4}\\b_{5}\\b_{6}\\b_{7}\end{Vmatrix}}+{\begin{Vmatrix}1\\1\\0\\0\\0\\1\\1\\0\end{Vmatrix}}}$

В процедуре ShiftRows байты в каждой строке state циклически сдвигаются влево. Размер смещения байтов каждой строки зависит от её номера

ShiftRows работает со строками State. При этой трансформации строки состояния циклически сдвигаются на r байт по горизонтали в зависимости от номера строки. Для нулевой строки r = 0, для первой строки r = 1 Б и т. д. Таким образом, каждая колонка выходного состояния после применения процедуры ShiftRows состоит из байтов из каждой колонки начального состояния. Для алгоритма Rijndael паттерн смещения строк для 128- и 192-битных строк одинаков. Однако для блока размером 256 бит отличается от предыдущих тем, что 2-е, 3-и и 4-е строки смещаются на 1, 3 и 4 байта соответственно. Это замечание не относится к AES, так как он использует алгоритм Rijndael только с 128-битными блоками, независимо от размера ключа.

В процедуре MixColumns каждая колонка состояния перемножается с фиксированным многочленом c(x).

В процедуре MixColumns четыре байта каждой колонки State смешиваются, используя для этого обратимую линейную трансформацию. MixColumns обрабатывает состояния по колонкам, трактуя каждую из них как полином третьей степени. Над этими полиномами производится умножение[6] в ${\displaystyle GF(2^{8})}$ по модулю ${\displaystyle x^{4}+1}$ на фиксированный многочлен ${\displaystyle c(x)=3x^{3}+x^{2}+x+2}$. Вместе с ShiftRows MixColumns вносит диффузию в шифр.

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

В процедуре AddRoundKey RoundKey каждого раунда объединяется со State. Для каждого раунда Roundkey получается из CipherKey c помощью процедуры KeyExpansion; каждый RoundKey такого же размера, что и State. Процедура производит побитовый XOR каждого байта State с каждым байтом RoundKey.

Алгоритм AES, используя процедуру KeyExpansion() и подавая в неё Cipher Key, K, получает ключи для всех раундов. Всего получается Nb*(Nr + 1) слов: изначально для алгоритма требуется набор из Nb слов, и каждому из Nr раундов требуется Nb ключевых набора данных. Полученный массив ключей для раундов обозначается как ${\displaystyle w\left[i\right]}$, ${\displaystyle 0\leq i<Nb*(Nr+1)}$. Алгоритм KeyExpansion() показан в псевдокоде ниже.

Функция SubWord() берёт четырёхбайтовое входное слово и применяет S-box к каждому из четырёх байтов. То, что получилось, подаётся на выход. На вход RotWord() подаётся слово ${\displaystyle [a_{0},a_{1},a_{2},a_{3}]}$, которое она циклически переставляет и возвращает ${\displaystyle [a_{1},a_{2},a_{3},a_{0}]}$. Массив слов, постоянный для данного раунда, ${\displaystyle Rcon\left[i\right]}$, содержит значения ${\displaystyle [x^{i-1},{00},{00},{00}]}$, где x = {02}, а ${\displaystyle x^{i-1}}$ является степенью ${\displaystyle x}$ в ${\displaystyle GF\left(2^{8}\right)}$ (${\displaystyle i}$ начинается с 1).

Из рисунка можно видеть, что первые ${\displaystyle Nk}$ слов расширенного ключа заполнены Cipher Key. В каждое последующее слово, ${\displaystyle w[i]}$, кладётся значение, полученное при операции XOR ${\displaystyle w[i-1]}$ и ${\displaystyle w\left[{i-Nk}\right]}$, те XOR’а предыдущего и на Nk позиций раньше слов. Для слов, позиция которых кратна Nk, перед XOR’ом к w[i-1] применяется трансформация, за которой следует XOR с константой раунда Rcon[i]. Указанная выше трансформация состоит из циклического сдвига байтов в слове (RotWord()), за которой следует процедура SubWord() — то же самое, что и SubBytes(), только входные и выходные данные будут размером в слово.

Важно заметить, что процедура KeyExpansion() для 256-битного Cipher Key немного отличается от тех, которые применяются для 128- и 192- битных шифроключей. Если ${\displaystyle Nk=8}$ и ${\displaystyle i-4}$ кратно ${\displaystyle Nk}$, то SubWord() применяется к ${\displaystyle w[i-1]}$ до XOR’а.

KeyExpansion(byte key[4 * Nk], word w[Nb * (Nr+1)], Nk)
begin
    word temp
    i = 0;
    
    while(i < Nk)
        w[i] = word(key[4*i], key[4*i+1], key[4*i+2], key[4*i+3])
        i = i + 1
    end while
    
    i = Nk

    while(i < Nb * (Nr+1))
        temp = w[i - 1]
        if (i mod Nk = 0)
            temp = SubWord(RotWord(temp)) xor Rcon[i / Nk]
        else if (Nk > 6 and i mod Nk = 4)
            temp = SubWord(temp)
        end if
        w[i] = w[i - Nk] xor temp
        i = i + 1
    end while
end

Псевдокод для Key Expansion

InvCipher(byte in[4 * Nb], byte out[4 * Nb], word w[Nb * (Nr+1)])
begin
    byte state[4, Nb]
    
    state = in

    AddRoundKey(state, w[Nr * Nb, Nb * (Nr+1) - 1])

    for round = Nr - 1 step -1 downto 1
        InvShiftRows(state)
        InvSubBytes(state)
        AddRoundKey(state, w[Nb * round, Nb * (round+1) - 1])
        InvMixColumns(state)
    end for

    InvShiftRows(state)
    InvSubBytes(state)
    AddRoundKey(state, w[0, Nb - 1])

    out = state
end

Псевдокод для Inverse Cipher

На каждой итерации ${\displaystyle i}$ раундовый ключ для операции AddRoundKey выбирается из массива ${\displaystyle w\left[i\right]}$,начиная с элемента ${\displaystyle w\left[Nb*i\right]}$ до ${\displaystyle w\left[Nb*\left(i+1\right)\right]}$.

В отличие от большинства других шифров, AES имеет простое математическое описание. Это беспокоило в том числе и Нильса Фергюсона, который в своей работе отметил, что безопасность шифра основывается на новом непроверенном предположении о сложности решения определённых видов уравнений (англ. «The security of Rijndael depends on a new and untested hardness assumption: it is computationally infeasible to solve equations of this type»)[8][9], а также Брюса Шнайера, который написал в совместной с Нильсом книге:

У нас есть одно критическое замечание к AES: мы не совсем доверяем его безопасности. Что беспокоит нас больше всего в AES, так это его простая алгебраическая структура… Ни один другой блочный шифр не имеет столь простого алгебраического представления. Мы понятия не имеем, ведёт это к атаке или нет, но незнание этого является достаточной причиной, чтобы скептически относиться к использованию AES.

Оригинальный текст (англ.)[показатьскрыть]

We have one criticism of AES: we don't quite trust the security… What concerns us the most about AES is its simple algebraic structure… No other block cipher we know of has such a simple algebraic representation. We have no idea whether this leads to an attack or not, but not knowing is reason enough to be skeptical about the use of AES

— Niels Ferguson, Bruce Schneier Practical Cryptography — 2003 — pp. 56—57

Николя Куртуа (англ. Nicolas Courtois) и Йозеф Пепшик (англ. Josef Pieprzyk) в 2002 году опубликовали статью, в которой описали теоретическую атаку, названную ими XSL-атакой (англ. eXtended Sparse Linearization), которая могла бы позволить вскрыть шифры AES и Serpent[10][11]. Тем не менее, результаты работы не всеми были восприняты оптимистично:

Я считаю, что в работе Куртуа-Пепшика есть ошибка. Они переоценили число линейно-независимых уравнений. В результате у них нет достаточного количества линейных уравнений для решения системы, и [указанный] метод не может взломать Rijndael. Он имеет определённые достоинства и заслуживает изучения, но не взламывает Rijndael в его нынешнем виде.

Оригинальный текст (англ.)[показатьскрыть]

I believe that the Courtois-Pieprzyk work is flawed. They overcount the number of linearly independent equations. The result is that they do not in fact have enough linear equations to solve the system, and the method does not break Rijndael… The method has some merit, and is worth investigating, but it does not break Rijndael as it stands.

— Дон Копперсмит, комментарий к записи в блоге Брюса Шнайера

На странице, посвящённой обсуждению конкурса NESSIE, в конце 2002 года один из авторов шифра, Винсент Рэймен, заявил, что XSL-атака является всего лишь мечтой (англ. The XSL attack is not an attack. It is a dream) (данная точка зрения позже была повторена в 2004 году на 4-й конференции AES в Бонне). На это Куртуа ответил, что данная мечта может стать для автора AES кошмаром (англ. It may also be a very bad dream and turn into a nightmare)[12] (игра слов: dream переводится и как мечта и как сновидение. Nightmare переводится как кошмарный сон, ночной кошмар).

В 2003 году Шон Мёрфи и Мэтт Робшоу (англ. Matt Robshaw) опубликовали работу, в которой (в предположении, что результаты Куртуа и Пепшика верны) обосновали возможность атаки на алгоритм AES, сокращающей количество операций для взлома с 2¹²⁸ до 2¹⁰⁰. Однако на 4-й конференции AES Илья Толи (англ. Ilia Toli) и Альберто Дзанони (англ. Alberto Zanoni) показали, что работа Мёрфи и Робшоу неверна[13]. Позже, в 2007 году, Чу-Ви Лим (англ. Chu-Wee Lim) и Хунгминг Ху (англ. Khoongming Khoo) также показали, что данная атака не может работать в том виде, как она была описана[14].

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

В апреле 2005 года Дэниел Бернштейн (англ. Daniel J. Bernstein) опубликовал работу с описанием атаки, использующей для взлома информацию о времени выполнения каждой операции шифрования[15]. Данная атака потребовала более 200 миллионов выбранных шифротекстов для нахождения ключа[16].

В октябре 2005 года Даг Арне Освик, Ади Шамир и Эран Трумер представили работу с описанием нескольких атак, использующих время выполнения операций для нахождения ключа. Одна из представленных атак получала ключ после 800 операций шифрования. Атака требовала от криптоаналитика возможности запускать программы на той же системе, где выполнялось шифрование[17].

В декабре 2009 года была опубликована работа, в которой использование дифференциального анализа ошибок (англ. Differential Fault Analysis), искусственно создаваемых в матрице состояния на 8-м раунде шифрования, позволило восстановить ключ за 2³² операций[18].