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

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

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

Содержание

История AES

[править |править код]
Основная статья:AES (конкурс)

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

Описание AES

[править |править код]

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

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

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}    };
Вспомогательные процедуры
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 в 32-битных словах используется нотация Nb = 4 для input и State, Nk = 4, 6, 8 для Cipher Key соответственно для разных длин ключей.

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

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

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

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 = stateend

SubBytes()

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

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

bi=bib(i+4)mod8b(i+5)mod8b(i+6)mod8b(i+7)mod8ci{\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}}

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

b0b1b2b3b4b5b6b7=1000111111000111111000111111000111111000011111000011111000011111b0b1b2b3b4b5b6b7+11000110{\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()

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

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

MixColumns()

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

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

AddRoundKey()

[править |править код]
В процедуре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 ключевых набора данных. Полученный массив ключей для раундов обозначается какw[i]{\displaystyle w\left[i\right]},0i<Nb(Nr+1){\displaystyle 0\leq i<Nb*(Nr+1)}. Алгоритм KeyExpansion() показан в псевдокоде ниже.

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

Из рисунка можно видеть, что первыеNk{\displaystyle Nk} слов расширенного ключа заполнены Cipher Key. В каждое последующее слово,w[i]{\displaystyle w[i]}, кладётся значение, полученное при операции XORw[i1]{\displaystyle w[i-1]} иw[iNk]{\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- битных шифроключей. ЕслиNk=8{\displaystyle Nk=8} иi4{\displaystyle i-4} кратноNk{\displaystyle Nk}, то SubWord() применяется кw[i1]{\displaystyle w[i-1]} до XOR’а.

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

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 whileend

Расшифрование

[править |править код]

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

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 = stateend

Алгоритм выбора раундового ключа

[править |править код]

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

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

[править |править код]

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

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

[править |править код]

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

XSL-атака

[править |править код]
Основная статья:XSL-атака

В отличие от большинства других шифров, 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, сокращающей количество операций для взлома с 2128 до 2100. Однако на 4-й конференции AES Илья Толи (англ. Ilia Toli) и Альберто Дзанони (англ. Alberto Zanoni) показали, что работа Мёрфи и Робшоу неверна[13]. Позже, в 2007 году, Чу-Ви Лим (англ. Chu-Wee Lim) и Хунгминг Ху (англ. Khoongming Khoo) также показали, что данная атака не может работать в том виде, как она была описана[14].

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

[править |править код]
Основная статья:Атака по сторонним каналам

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

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

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

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

Квантовая угроза

[править |править код]
Основная статья:Квантовое превосходство

Национальный институт стандартов и технологий США (NIST), определяющий национальную политику и стандарты, объявил, что, по его прогнозам, к 2029 г.квантовые компьютеры смогут взломать 128-битноеAES-шифрование, которым пользуются многие компании[19].

См. также

[править |править код]

Примечания

[править |править код]
  1. Лаборатория Чеканова. Intel Core i5 (Clarkdale): анализ аппаратного ускорения шифрования AES  (рус.). THG (19 января 2010). — «наиболее популярный стандарт симметричного шифрования в мире ИТ». Дата обращения: 14 ноября 2010. Архивировано 26 февраля 2012 года.
  2. Biryukov, Alex and Khovratovich, Dmitry. Related-key Cryptanalysis of the Full AES-192 and AES-256 (англ.) // Advances in Cryptology – ASIACRYPT 2009. — Springer Berlin / Heidelberg, 2009. —Vol. 5912. —P. 1—18. —doi:10.1007/978-3-642-10366-7_1. Архивировано 18 декабря 2010 года.
  3. Архивированная копия . Дата обращения: 7 декабря 2006. Архивировано изоригинала 6 ноября 2006 года.
  4. NIST Error PageАрхивировано 28 сентября 2010 года.
  5. Bounce to index.htmlАрхивировано 17 июля 2014 года.
  6. http://csrc.nist.gov/publications/fips/fips197/fips-197.pdfАрхивная копия от 7 апреля 2015 наWayback Machine «5.1.3 MixColumns() Transformation .. The columns are considered as polynomials over GF(2^8) and multiplied modulo x^4 + 1 with a fixed polynomial a(x), given by a(x) = {03}x3 + {01}x2 + {01}x + {02}.»
  7. National Policy on the Use of the Advanced Encryption Standard (AES) to Protect National Security Systems and National Security Information (англ.). Committee on National Security Systems (июнь 2003). Дата обращения: 27 октября 2010. Архивировано 19 февраля 2012 года.
  8. James McLaughlin. The XSL controversy // A survey of block cipher cryptanalysis techniques. — preprint. — York:University of York, 2009. (недоступная ссылка)
  9. Niels Ferguson, Richard Schroeppel, and Doug Whiting. A simple algebraic representation of Rijndael (англ.) // Selected Areas in Cryptography, Proc. SAC 2001, Lecture Notes in Computer Science #2259. — Springer Verlag, 2001. —P. 103—111. Архивировано 16 января 2016 года.
  10. Bruce Schneier. Crypto-Gram Newsletter (англ.). Schneier on Security (15 сентября 2002). Дата обращения: 27 октября 2010. Архивировано 19 февраля 2012 года.
  11. Nicolas Courtois, Josef Pieprzyk. Cryptanalysis of Block Ciphers with Overdefined Systems of Equations (англ.) // Advances in Cryptology — ASIACRYPT 2002 8th International Conference on the Theory Application of Cryptology and Information Security Queenstown, New Zealand, December 1—5, 2002 Proceedings. Lecture Notes in Computer Science (2501). — Springer, 2002. —P. 267—287. —doi:10.1007/3-540-36178-2. Архивировано 26 октября 2020 года.
  12. NESSIE Discussion Forum
  13. Ilia Toli, Alberto Zanoni. An Algebraic Interpretation of AES-128 (недоступная ссылка —история) (англ.) // Proc. of AES Conference. — 2005. —Vol. 2005. —P. 84—97. —doi:10.1007/11506447_8.
  14. Chu-wee Lim, Khoongming Khoo. An Analysis of XSL Applied to BES (недоступная ссылка —история) (англ.) // Fast Software Encryption. — Heidelberg: Springer Berlin / Heidelberg, 2007. —Vol. 4593. —P. 242—253. —doi:10.1007/978-3-540-74619-5_16.
  15. Daniel J. Bernstein. Cache-timing attacks on AES (англ.). — 2004. Архивировано 17 сентября 2008 года.
  16. Bruce Schneier. AES Timing Attack (англ.). Schneier on Security (17 мая 2005). Дата обращения: 27 октября 2010. Архивировано 19 февраля 2012 года.
  17. Dag Arne Osvik; Adi Shamir and Eran Tromer. Cache Attacks and Countermeasures: the Case of AES // Topics in Cryptology — CT-RSA 2006, The Cryptographers’ Track at the RSA Conference. — Springer-Verlag, 2005. — P. 1—20. Архивировано 25 ноября 2020 года.
  18. Dhiman Saha, Debdeep Mukhopadhyay, Dipanwita RoyChowdhury. A Diagonal Fault Attack on the Advanced Encryption Standar (англ.) // Cryptology ePrint Archive. — 2009. Архивировано 6 августа 2020 года.
  19. Каку, 2024, с. 20.

Литература

[править |править код]

Ссылки

[править |править код]
Перейти к шаблону «External links»
Ссылки на внешние ресурсы
Перейти к шаблону «Внешние ссылки» Перейти к элементу Викиданных
  Словари и энциклопедии
Перейти к шаблону «Симметричные криптосистемы»
Потоковые шифры
Сеть Фейстеля
SP-сеть
Другие
Источник —https://ru.wikipedia.org/w/index.php?title=AES_(стандарт_шифрования)&oldid=150601638
Категории:
Скрытые категории: