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

AES, Rijndael-AES, Rijndael
Создатель	Винсент Рэймен, Йоан Даймен
Создан	1998 г.
Опубликован	2001 г.
Размер ключа	128/192/256 бит
Размер блока	128 бит
Число раундов	10/12/14 (зависит от размера ключа)
Тип	Подстановочно-перестановочная сеть
Медиафайлы на Викискладе

Advanced Encryption Standard (AES), также известный как Rijndael (произносится rɛindaːl) — симметричный алгоритм блочного шифрования (размер блока 128 бит, ключ 128/192/256 бит), принятый в качестве стандарта шифрования правительством США по результатам конкурса AES. Этот алгоритм хорошо проанализирован и сейчас широко используется, как это было с его предшественником DES. Национальный институт стандартов и технологий США (англ. National Institute of Standards and Technology, NIST) опубликовал спецификацию AES 26 ноября 2001 года после пятилетнего периода, в ходе которого были созданы и оценены 15 кандидатур. 26 мая 2002 года AES был объявлен стандартом шифрования. По состоянию на 2006 год AES является одним из самых распространённых алгоритмов симметричного шифрования.

История AES

Основная статья: AES (конкурс)

2 января 1997 года NIST объявляет о намерении выбрать преемника для DES, являвшегося американским стандартом с 1977 года. 2 октября 2000 года было объявлено, что победителем конкурса стал алгоритм Rijndael, и началась процедура стандартизации. 28 февраля 2001 года был опубликован проект, а 26 ноября 2001 года AES был принят как FIPS 197. Историческую ретроспективу конкурса можно проследить на веб-сайте NIST .

Описание AES

Определения и вспомогательные процедуры

Определения

Block	последовательность бит, из которых состоит input, output, State и Round Key. Также под Block можно понимать последовательность байт
Cipher Key	секретный, криптографический ключ, который используется Key Expansion процедурой, чтобы произвести набор ключей для раундов(Round Keys); может быть представлен как прямоугольный массив байтов, имеющий четыре строки и Nk колонок.
Ciphertext	выходные данные алгоритма шифрования
Key Expansion	процедура используемая для генерации Round Keys из Cipher Key
Round Key	Round Keys получаются из Cipher Key используя процедуру Key Expansion. Они применяются к State при шифровании и расшифровании
State	промежуточный результат шифрования, который может быть представлен как прямоугольный массив байтов имеющий 4 строки и Nb колонок
S-box	нелинейная таблица замен, использующаяся в нескольких трансформациях замены байт и в процедуре Key Expansion для взаимнооднозначной замены значения байта
Nb	число столбцов(32-ух битных слов), составляющих State. Для, AES Nb = 4
Nk	число 32-ух битных слов, составляющих шифроключ. Для AES, Nk = 4,6, или 8
Nr	число раундов, которое является функцией Nk и Nb. Для AES, Nr = 10, 12, 14
Rcon[]	массив, который состоит из битов 32-х разрядного слова и является постоянным для данного раунда

Вспомогательные процедуры

AddRoundKey()	трансформация при шифровании и обратном шифровании, при которой Round Key XOR’ится c State. Длина RoundKey равна размеру State(те, если Nb = 4, то длина RoundKey равна 128 бит или 16 байт)
InvMixColumns()	трансформация при расшифровании которая является обратной по отношению к MixColumns()
InvShiftRows()	трансформация при расшифровании которая является обратной по отношению к ShiftRows()
InvSubBytes()	трансформация при расшифровании которая является обратной по отношению к SubBytes()
MixColumns()	трансформация при шифровании которая берет все столбцы State и смешивает их данные (независимо друг от друга), чтобы получить новые столбцы
RotWord()	функция, использующаяся в процедуре Key Expansion, которая берет 4-х байтное слово и производит над ним циклическую перестановку
ShiftRows()	трансформации при шифровании, которые обрабатывают State, циклически смещая последние три строки State на разные величины
SubBytes()	трансформации при шифровании которые обрабатывают State используя нелинейную таблицу замещения байтов(S-box), применяя её независимо к каждому байту State
SubWord()	функция, используемая в процедуре Key Expansion, которая берет на входе четырёх-байтное слово и применяя S-box к каждому из четырёх байтов выдаёт выходное слово

Шифрование

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

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

Шифр описан в псевдокоде на рис1. Отдельные трансформации 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()

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

Процедура SubBytes() обрабатывает каждый байт состояния, независимо производя нелинейную замену байтов используя таблицу замен(S-box). Такая операция обеспечивает нелинейность алгоритма шифрования. Построение S-box состоит из двух шагов. Во-первых, производится взятие обратного числа в GF{$2^{8}$}. Во-вторых, к каждому байту b из которых состоит S-box применяется следующая операция: $b_{i}^{'}=b_{i}\oplus b_{(i+4)mod8}\oplus b_{(i+5)mod8}\oplus b_{(i+6)mod8}\oplus b_{(i+7)mod8}\oplus c_{i}$, где $0\leq i<8$, и где b_i есть i-ый бит b, а c_i — i-ый бит c = {63} или {01100011}. Таким образом, обеспечивается защита от атак, основанных на простых алгебраических свойствах.

${\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()

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

.

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

MixColumns()

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

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

AddRoundKey()

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

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

KeyExpansion()

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

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

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

Важно заметить, что процедура KeyExpansion() для 256 битного Cipher Key немного отличается от тех, которые применяются для 128 и 192 битных шифроключей. Если Nk = 8 и i — 4 кратно Nk, то SubWord() применяется к 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

Рис.6 Псевдокод для 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, (Nr+1)*Nb-1])

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

    InvShiftRows(state)
    InvSubBytes(state)
    InvAddRoundKey(state, w[Nr*Nb, (Nr+1)*Nb-1])

    out = state
end

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

Варианты алгоритма

На базе алгоритма Rijndael, лежащего в основе AES, реализованы альтернативные криптоалгоритмы. Среди наиболее известных — участники конкурса Nessie: Anubis на инволюциях, автором которого является Винсент Рэймен и усиленный вариант шифра — Grand Cru Йохана Борста.

Криптостойкость

В июне 2003 года Агентство национальной безопасности США постановило, что шифр AES является достаточно надёжным, чтобы использовать его для защиты сведений, составляющих государственную тайну (англ. classified information). Вплоть до уровня SECRET было разрешено использовать ключи длиной 128 бит, для уровеня TOP SECRET требовались ключи длиной 192 и 256 бит.

XSL-атака

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

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. Тем не менее, результаты работы не всеми были восприняты оптимистично:

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 в Бонне). На это Courtois ответил, что данная мечта может стать для автора AES кошмаром (англ. It may also be a very bad dream and turn into a nightmare).

В 2003 году Sean Murphy и Matt Robshaw опубликовали работу, в которой, в предположении что результаты Courtois и Pieprzyk верны, обосновали возможность атаки на алгоритм AES, сокращающей количество операций для взлома с 2¹²⁸ до 2¹⁰⁰. Однако на на 4-й конференции AES Toli и Zanoni показали, что работа Мёрфи и Робшава неверна. Позже, в 2007 году, Chu-Wee Lim и Khoongming Khoo показали, что данная атака не может работать в том виде, как она была описана.

Атака по сторонним каналам

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

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

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

В декабре 2009 года была опубликована работа, в которой использование дифференциального анализа ошибок (англ. ) позволило восстановить ключ за 2³² операций.

См. также

• Тестирование алгоритмов, участвовавших в конкурсе AES

Ссылки

• О процессе принятия AES  (рус.)
• Перевод стандарта FIPS 197 (AES)  (рус.)
• Federal Information Processing Standards Publication 197 November 26, 2001 Specification for the ADVANCED ENCRYPTION STANDARD (AES)  (англ.)