Как устроен AES
О чём эта статья
Долгое время я считал, что криптографические алгоритмы шифрования и хеширования, вроде AES и MD5, устроены очень сложно и написать их совсем не просто, даже имея под рукой полную документацию. Запутанные реализации этих алгоритмов на разных языках программирования только укрепляли это мнение. Но недавно у меня появилось много свободного времени и я решил разобраться в этих алгоритмах и написать их. Оказалось, что они очень просто устроены и для их реализации нужно совсем немного времени.
В этой статье я напишу как устроен алгоритм шифрования AES (которого иногда называют Rijndael) и напишу его на JavaScript. Почему на JavaScript? Чтобы запустить программу на этом языке, нужен только браузер в котором вы читаете эту статью. Чтобы запустить программу, скажем, на C, нужен компилятор и найдётся совсем мало желающих, готовых потратить время на компиляцию кода из какой то статьи. В конце есть ссылка по которой можно скачать архив с html страницей и несколькими js файлами — это пример реализации AES на JavaScript.
Как применить AES
Этот алгоритм преобразует один 128-битный блок в другой, используя секретный ключ который нужен для такого преобразования. Для расшифровки полученного 128-битного блока используют второе преобразование с тем же секретным ключом. Выглядит это так:
Размер блока всегда равен 128 бит. Размер ключа также имеет фиксированный размер. Чтобы зашифровать произвольный текст любым паролем можно поступить так:
Это можно записать так:
Чтобы расшифровать массив блоков cipher нужно применить к каждому блоку decrypt:
Конечно, длина текста может быть не кратна 128 битам. В таких случаях можно дополнить текст нулями до нужной длины, а в зашифрованные данные добавить несколько байт с зашифрованным размером оригинального текста. Функции aes.encrypt и aes.decrypt в файле aes.js в примере используют этот подход.
Поле GF(2 8 )
AES активно использует так называемое конечное поле GF(2 8 ). Чтобы написать AES на JavaScript не обязательно знать, что это за поле, но если вы хотите лучше понять AES, прочтите этот раздел.
Поле GF(2 8 ) это числа 0..255 для которых определили особое умножение и особое сложение. Возмём какое нибудь число из этого поля и представим его в виде восьми битов: a = a7a6a5a4a3a2a1a0. Точно также представим число b. Сложение a и b это известная побитовая операция xor:
У сложения есть простые свойства:
Умножение определяется сложнее. Запишем многочлены с коэффициентами из битов этих чисел:
Теперь перемножим эти два многочлена и найдём остаток от деления на m:
m = x 8 + x 4 + x 3 + x + 1
r = pq mod (m)
Почему выбран именно такой m? У этого многочлена есть только два делителя-многочлена на которых он делится без остатка: единица и он сам. По аналогии с простыми числами, многочлен m «простой». Находить остаток от деления можно также как для обычных чисел: для этого достаточно уметь умножать, складывать и вычитать многочлены, причём сложение и вычитание производят по правилам GF(2 8 ), т.е. сложение и вычитание многочленов это xor между каждой парой коэффициентов. Вот два примера:
Многочлен r представим в виде
Его 8 коэффициентов представляют собой 8-битовое число из поля GF(2 8 ) и это число называется произведением a•b. В отличие от сложения, умножение нельзя найти парой простых побитовых операций. Однако умножение на произвольный многочлен в поле GF(2 8 ) можно свести к умножению на многочлен x, а умножить на x можно несколькими побитовыми операциями, о чём пойдёт речь ниже.
Для обозначения многочленов в GF(2 8 ) используют 16-ричные цифры. Например
m = x 8 + x 4 + x 3 + x + 1 = 100011011 = 0x011b = <01><1b>
Умножить на многочлен x = <02>в поле GF(2 8 ) очень просто. Рассмотрим произведение:
Теперь нужно найти остаток от деления на m. Если бит a7 = 1, то нужно один раз вычесть m. Если a7 = 0 то вычитать ничего не нужно. Итак:
Умножение на x можно записать такой функцией:
Зная как умножать на x можно умножить на любой другой многочлен. Для примера найдём a•b где a = <3c>, b =
Таблица SBox
Эта таблица представляет собой 256-байтый массив и используется для замены одного байта другим. Не обязательно понимать как она получается, потому что в код можно просто скопировать этот массив. Чтобы узнать чему равен элемент SBox[b] нужно три действия:
В сумме эти три действия дают афинное преобразование:
Несложно понять как построена эта матрица из битов. Для умножения битов нужно применять «and», для сложения — «xor». Например:
Функцию sbox я написал так:
Построенная таблица выглядит так:
63 7c 77 7b f2 6b 6f c5 30 01 67 2b fe d7 ab 76
ca 82 c9 7d fa 59 47 f0 ad d4 a2 af 9c a4 72 c0
b7 fd 93 26 36 3f f7 cc 34 a5 e5 f1 71 d8 31 15
04 c7 23 c3 18 96 05 9a 07 12 80 e2 eb 27 b2 75
09 83 2c 1a 1b 6e 5a a0 52 3b d6 b3 29 e3 2f 84
53 d1 00 ed 20 fc b1 5b 6a cb be 39 4a 4c 58 cf
d0 ef aa fb 43 4d 33 85 45 f9 02 7f 50 3c 9f a8
51 a3 40 8f 92 9d 38 f5 bc b6 da 21 10 ff f3 d2
cd 0c 13 ec 5f 97 44 17 c4 a7 7e 3d 64 5d 19 73
60 81 4f dc 22 2a 90 88 46 ee b8 14 de 5e 0b db
e0 32 3a 0a 49 06 24 5c c2 d3 ac 62 91 95 e4 79
e7 c8 37 6d 8d d5 4e a9 6c 56 f4 ea 65 7a ae 08
ba 78 25 2e 1c a6 b4 c6 e8 dd 74 1f 4b bd 8b 8a
70 3e b5 66 48 03 f6 0e 61 35 57 b9 86 c1 1d 9e
e1 f8 98 11 69 d9 8e 94 9b 1e 87 e9 ce 55 28 df
8c a1 89 0d bf e6 42 68 41 99 2d 0f b0 54 bb 16
Её можно просто скопировать в код, как часто делают, а можно вычислять функцией sbox по мере надобности.
Таблица InvSBox
Для дешифрования текста AES использует таблицу обратную к SBox. Таблица InvSBox обладает одним свойством: InvSBox[SBox[i]] = i. InvSBox выглядит так:
52 09 6a d5 30 36 a5 38 bf 40 a3 9e 81 f3 d7 fb
7c e3 39 82 9b 2f ff 87 34 8e 43 44 c4 de e9 cb
54 7b 94 32 a6 c2 23 3d ee 4c 95 0b 42 fa c3 4e
08 2e a1 66 28 d9 24 b2 76 5b a2 49 6d 8b d1 25
72 f8 f6 64 86 68 98 16 d4 a4 5c cc 5d 65 b6 92
6c 70 48 50 fd ed b9 da 5e 15 46 57 a7 8d 9d 84
90 d8 ab 00 8c bc d3 0a f7 e4 58 05 b8 b3 45 06
d0 2c 1e 8f ca 3f 0f 02 c1 af bd 03 01 13 8a 6b
3a 91 11 41 4f 67 dc ea 97 f2 cf ce f0 b4 e6 73
96 ac 74 22 e7 ad 35 85 e2 f9 37 e8 1c 75 df 6e
47 f1 1a 71 1d 29 c5 89 6f b7 62 0e aa 18 be 1b
fc 56 3e 4b c6 d2 79 20 9a db c0 fe 78 cd 5a f4
1f dd a8 33 88 07 c7 31 b1 12 10 59 27 80 ec 5f
60 51 7f a9 19 b5 4a 0d 2d e5 7a 9f 93 c9 9c ef
a0 e0 3b 4d ae 2a f5 b0 c8 eb bb 3c 83 53 99 61
17 2b 04 7e ba 77 d6 26 e1 69 14 63 55 21 0c 7d
Виды AES
Алгоритм AES преобразует блок длиной 128 битов в другой блок той же длины. Для преобразования применяется расписание ключей w получаемое из ключа. 128-битный блок в AES представляется в виде матрицы 4×Nb. Стандарт допускает только одно значение Nb = 4, поэтому длина блока всегда 128 бит, хотя алгоритм может работать с любым Nb. Длина ключа равна 4Nk байт. Алгоритм шифрования блока состоит из Nr раундов — применений одной и той же группы преобразований к 128-битному блоку данных. Стандарт допускает следующие комбинации этих трёх параметров:
| Nk | Nb | Nr | |
| AES-128 | 4 | 4 | 10 |
| AES-192 | 6 | 4 | 12 |
| AES-256 | 8 | 4 | 14 |
Преобразование KeyExpansion
Для шифрования текста AES применяет не пароль или хеш от пароля, а так называемое «расписание ключей» получаемое из ключа. Это расписание можно представить как Nr + 1 матриц размера 4×Nb. Алгоритм шифрования делает Nr + 1 шагов и на каждом шаге он, помимо других действий, берёт одну матрицу 4×Nb из «расписания» и поэлементно добавляет её к блоку данных.
Шифрование блока данных
Алгоритм шифрования получает на вход 128-битный блок данных input и расписание ключей w, которое получается после KeyExpansion. 16-байтый input он записывает в виде матрицы s размера 4×Nb, которая называется состоянием AES, и затем Nr раз применяет к этой матрице 4 преобразования. В конце он записывает матрицу в виде массива и подаёт его на выход — это зашифрованный блок. Каждое из четырёх преобразований очень простое.
Для шифрования используют [a b c d] = [ <02><03><01><01>]. Можно проверить, что преобразование обратное к MixColumns[ <02><03><01><01>] это MixColumns[ <0e><0b><0d><09>].
Схематично шифрование можно изобразить так:
Расшифровка
Как видно, для шифрования блока данных AES последовательно применяет к нему много обратимых преобразований. Для расшифровки нужно применить обратные преобразования в обратном порядке.
Немного оптимизации
Функция sbox имеет всего 256 возможных входных значений и 256 возможных выходных значений. Чтобы не вычислять много раз sbox для одного аргумента, нужно кешировать результаты. На JavaScript это несложно сделать даже не меняя код написанный ранее. Для этого нужно всего лишь дописать ниже вот это:
Этот код заменяет sbox функцией которая кеширует результаты sbox. Тоже самое можно сделать для любой функции, например для invsbox и rcon. Этот же приём можно применить для функции gf.mul которая умножает два байта в поле GF(2 8 ), но в этом случае размер кеша будет равен 256×256 элементов, что довольно много.
Ссылки
Документация к AES на английском называется FIPS 197.
Описание основ криптопреобразования AES
Доброго времени суток, Хабр! Примерно 3 месяца назад проходил собеседование frontend разработчиком и самый первый вопрос, который мне задали: “Что такое AES?” Ну как бы аморфное представление я все же имел о симметрично блочном шифровании AES, было дело даже использовал в одном из проектов для шифрования персональных данных. Но чтобы знать алгоритм rijndael и еще уметь его реализовать на javascript, для меня на тот момент казалось задачей трудновыполнимой. Но! Мне был брошен вызов и я его принял.
Go в подкат!
За основу я взял спецификацию FIPS197 AES от 26 ноября 2011г.
В IT сфере одни из самых известных алгоритмов шифрования являются:
В свою очередь симметричные алгоритмы делятся на два типа:
Потоковые шифруют посимвольно.
Преимуществами для асимметричных алгоритмов является его безопасное хранение ключей. Асимметричные — те алгоритмы, которые имеют два ключа:
Недостатками асимметричных алгоритмов, является его относительно медленное выполнение шифрования.
Rijndael — симметричный алгоритм блочного шифрования с возможностью изменять размеры блоков и секретных ключей от 128 до 256 бит с разностью в 32 бита. Использует линейно-подстановочные преобразования и состоит из 10, 12 или 14 раундов в зависимости от длины ключа.
AES — rijndael с ключом в 128 бит и блоком данных в 16 байт.
Предположительно вы знакомы с теорией следующих терминов:
Математические понятия в rijndael:
a(x)=a₇x⁷ +a₆x⁶ +a₅x⁵ +a₄x⁴ +a₃x³ +a₂x² +a₁x +a₀x;
Байт А, состоящий из битов a₇, a₆, a₅, a₄, a₃, a₂, a₁, a₀;
Байт B, состоящий из битов b₇, b₆, b₅, b₄, b₃, b₂, b₁, b₀;
Произведение 87 x 131 будет выглядеть следующим образом:
(x⁶ + x⁴ + x² + x + 1)(x⁷ + x + 1) = x¹³ + x¹¹ + x⁹ + x⁸ + x⁷ + x⁷ + x⁵ + x³ + x² + x + x⁶ + x⁴ + x² + x + 1.
Раскрытие скобок происходит на основе элементарных математических правил. Далее сложение происходит по правилам суммирования указанных выше (п.4):
x⁷ + x⁷ = x⁷(1 + 1) = x⁷(1 ^ 1) = x⁷0 = 0;
(x⁶ + x⁴ + x² + x + 1)(x⁷ + x + 1) = x¹³ + x¹¹ + x⁹ + x⁸ + x⁶ + x⁵ + x⁴ + x³ + 1.
После производится деление на конкретно заданную функцию m(x) = x⁸ + x⁴ + x³ + x + 1 (неприводимый полином), которая по правилам rijndael гарантирует корректный результат, то есть на выходе мы получим двоичный полином степени меньше 8, а значит сможем представить его байтом для дальнейшего шифрования. Деление производится по модулю. Деление можно производить, как деление многочленов столбиком. Остаток от деления является результатом:
(x⁶ + x⁴ + x² + x + 1)(x⁷ + x + 1)/(x⁸ + x⁴ + x³ + x + 1) =
(x¹³ + x¹¹ + x⁹ + x⁸ + x⁶ + x⁵ + x⁴ + x³ + 1)/(x⁸ + x⁴ + x³ + x + 1) = |Result| = x⁷ + x⁶ + 1
Все вычислительные операции алгоритма проводятся с использованием вышеописанных правил
Функции алгоритма:
Шифрование в AES происходит в несколько этапов:
Rcon — постоянный массив для генерации ключей путем XOR. Иначе говоря функция keyExpansion() циклично XOR’ится с ключами фиксированного массива Rcon и возвращает массив ключей. Количество ключей составляет — 11. 10 из которых принадлежат раундам алгоритма.
Первый этап шифрования начинается с применения данной функции к state путем правила суммирования, указанного выше. Иначе говоря addRoundKey XOR’ится со state, точнее с каждым его байтом. Об’XOR’енный state попадает на следующий этап, а именно в систему раундов алгоритма:
В алгоритме есть 10 раундов, то есть 10 шагов криптопреобразования. Первые 9 раундов циклично выполняют 4 функции:
Данная функция трансформирует state путем замены своих байтов на другие способом подставления в готовую фиксированную таблицу S-box:
53h будет равен edh
Данная функция производит циклическое смещение 3-х последних строк влево следующим образом:
Вычислительно самое сложное из функций. Тут происходит умножение на постоянную функцию a(x) = <03>x³ + <01>x² + <01>x + <02>. То есть произведение по указанному выше правилу конкретного столбца из state на функцию a(x). За исключением правила умножения алгоритма данный способ эквивалентен матричному умножению:
Дешифрование в AES также происходит в несколько этапов:
В алгоритме есть 10 раундов, то есть шаг криптопреобразования.
Первые 9 раундов циклично выполняют 4 функции, порядок обратный порядку шифрования, то есть:
Функция invMixColumns выполняет мультипликативно обратную операцию умножения по правилам умножения алгоритма на постоянную функцию a⁻¹(x) конкретного столбца state:
Обратная трансформация shiftRows() — циклическое смещение вправо:
Инверсия subBytes() — обратная замена байт state заведомо представленную в hex в соответствии фиксированной таблицы inverse S-box:
Список литературы:
Алгоритм шифрования AES
После того как мы на прошлой неделе опубликовали информацию о готовящихся к продаже новых криптотелефонах X-Telecom Secure Mobile, в которых используется алгоритм шифрования AES-256, многие люди стали звонить и интересоваться, что это за алгоритм AES, насколько он надежен и удовлетворяет ли он требования информационной безопасности.
Алгоритм Advanced Encryption Standard
Advanced Encryption Standard – симметричный алгоритм блочного шифрования, принятый правительством США в качестве стандарта в результате конкурса, проведенного между технологическими институтами. Он заменил устаревший Data Encryption Standard, который больше не соответствовал требованиям сетевой безопасности, усложнившимся в XXI веке.
Этот алгоритм, кроме аббревиатуры AES, иногда называют еще Rijndael – это анаграмма из частей имен бельгийских программистов Joan Daemen и Vinent Rijmen, которые разработали AES. Строго говоря, AES и Rijndael – не совсем одно и то же, поскольку AES имеет фиксированный размер блока в 128 бит и размеры ключей в 128, 192 и 256 бит, в то время как для Rijndael могут быть заданы любые размеры блока и ключа, от минимума в 32 бит до максимума в 256 бит.
Алгоритм AES был одобрен Агентством национальной безопасности США как пригодный для шифрования особо секретной информации. Однако, правительство постановило, что AES должен периодически подвергаться проверкам и улучшениям, чтобы надежно хранить зашифрованные данные.
Информация, определенная как секретная, должна быть защищена посредством AES с длиной ключей 128, 192 и 256 бит. Для информации, определенной как особо секретная, эта длина составляет 192 или 256 бит. Суть AES в том, что любая «лобовая атака» на защищенные данные – то есть подбор всех возможных паролей – в перспективе очень сильно растягивается. Если представить, что взломщик располагает огромными ресурсами, то есть целой коллекцией суперкомпьютеров, то при усердном старании доступ к зашифрованным данным он мог бы получить через десятки лет. Если же в его распоряжении ничего этого нет, то взлом AES займет астрономически долгое время.
Надежность алгоритма шифрования AES
Считается, что используемый в Advanced Encryption Standard ключ длиной в 128 бит – достаточно надежная защита против лобовой атаки, то есть с чисто математической точки зрения подобрать один правильный пароль из всех возможных – трудноосуществимая задача. Несмотря даже на некоторые недостатки AES, взломать защищенную с помощью этого алгоритма информацию практически нереально.
Любой криптографический алгоритм требует ключ размером в то или иное количество бит, чтобы зашифровать данные, как показано в схеме №1.
Длина ключа, используемая при шифровании и определяет практическую целесообразность выполнения полного перебора, ведь информацию зашифрованную более длинными ключами экспоненциально сложнее взломать, чем с короткими.
Вот пример перебора 4-битного ключа:
Потребуется максимум 16 стадий, чтобы проверить каждую возможную комбинацию, начиная с «0000». Лобовая атака за некоторое время может пробить такой простой алгоритм.
Таблица на рисунке ниже показывает возможное число комбинаций с учетом размера ключа:
Обратите внимание на то, что по мере увеличения размера ключа количество комбинаций возрастает экспоненциально. Математические исчисления доказывают, что размер ключа в 128 бит надежнейшим образом защищает от лобовой атаки:
Таким образом, даже суперкомпьютеру понадобилось бы неисчислимо огромное количество времени, чтобы получить доступ к информации под защитой AES посредством лобовой атаки.
Для сравнения: возраст Вселенной – где-то между 13 и 14 миллиардами лет. Даже если предположить, что некий супер-суперкомпьютер мог быть справляться с алгоритмом DES за одну секунду, то на взлом AES у него ушло бы около 149 триллионов лет.
Как видите, размера ключа в 128 бит вполне достаточно, хотя совершенно секретная информация все равно шифруется с размером в 256 бит. Следующее предположение доказывает, что стандарт 128 бит будет оставаться актуальным и в будущем.
При всех этих условиях все население планеты смогло бы взломать один ключ… за 77,000,000,000,000,000,000,000,000 лет.
При этом интересно отметить, что разница между размером ключа в 128 бит и 256 бит не так уж принципиальна. Если бы кто-то придумал бы некую программу, способную взломать 128-битную систему, то 256 бит для этого гения не были бы помехой.
Наконец, лучше всего за AES говорит статистика: защищенные этим алгоритмом данные никогда не были взломаны. Впрочем, все это работает при размере ключа минимум в 128 бит, поскольку более ранние шифровальные алгоритмы все же не выдерживали испытания на прочность.
Несмотря на то, что скорость вычисления компьютеров увеличивается в геометрической прогрессии согласно закону Мура, 128-битного ключа вполне должно хватить на много лет вперед.
Таким образом, все звонки и сообщения в криптотелефонах X-Telecom шифруются очень надежно, ведь кроме AES-256 еще дополнительно используется алгоритм Twofish и несколько вспомогательных алгоритмов — в комплексе это дает совершенную 100%-ую защиту вашего общения от прослушки любыми современными способами.
Лучший в своем классе: история появления стандарта шифрования AES
C мая 2020 года в России стартовали официальные продажи внешних винчестеров WD My Book, поддерживающих аппаратное шифрование AES с 256-битным ключом. В силу законодательных ограничений, ранее подобные устройства можно было приобрести лишь в зарубежных интернет-магазинах электроники либо на «сером» рынке, однако теперь обзавестись защищенным накопителем с фирменной 3-летней гарантией от Western Digital может любой желающий. В честь этого знаменательного события мы решили сделать небольшой экскурс в историю и разобраться, как появился Advanced Encryption Standard и чем же он так хорош по сравнению с конкурирующими решениями.
Долгое время официальным стандартом симметричного шифрования в США являлся DES (Data Encryption Standard — стандарт шифрования данных), разработанный компанией IBM и внесенный в перечень Федеральных стандартов обработки информации в 1977 году (FIPS 46-3). В основу алгоритма легли наработки, полученные в ходе исследовательского проекта под кодовым названием Lucifer. Когда 15 мая 1973 года Национальное бюро стандартов США объявило о проведении конкурса, целью которого стало создание стандарта шифрования для госучреждений, американская корпорация включилась в криптографическую гонку с третьей версией Люцифера, использовавшей обновленную сеть Фейстеля. И наряду с другими конкурсантами потерпела фиаско: ни один из алгоритмов, представленных на первый конкурс, не соответствовал строгим требованиям, сформулированным экспертами НБС.
Разумеется, в IBM не могли просто так смириться с поражением: когда 27 августа 1974 года конкурс был перезапущен, американская корпорация вновь подала заявку, представив улучшенную версию Lucifer. На сей раз у жюри не оказалось ровным счетом ни одной претензии: проведя грамотную работу над ошибками, IBM успешно устранила все недочеты, так что придраться оказалось не к чему. Одержав убедительную победу, Люцифер сменил имя на DES и уже 17 марта 1975 года был издан в Федеральном реестре.
Однако в ходе открытых симпозиумов, организованных в 1976 году с целью обсуждения нового криптографического стандарта, DES подвергся жесткой критике со стороны экспертного сообщества. Причиной этого стали изменения, внесенные в алгоритм специалистами АНБ: в частности, была уменьшена длина ключа до 56 бит (изначально Lucifer поддерживал работу с 64- и 128-битными ключами), а также изменена логика работы блоков перестановки. По мнению криптографов, «улучшения» не имели смысла и единственное, к чему стремилось Агентство национальной безопасности, внедряя модификации, — получить возможность беспрепятственно просматривать зашифрованные документы.
В связи с перечисленными обвинениями, при Сенате США была создана специальная комиссия, целью работы которой стала проверка обоснованности действий АНБ. В 1978 году по итогам расследования был опубликован доклад, в котором сообщалось следующее:
В то же время ограничение на длину ключа оказалось проблемой, и притом весьма серьезной, что в 1998 году убедительно доказала общественная организация Electronic Frontier Foundation (EFF) в рамках эксперимента DES Challenge II, проведенного под эгидой RSA Laboratory. Специально для взлома DES был построен суперкомпьютер, получивший кодовое название EFF DES Cracker, над созданием которого трудились Джон Гилмор, сооснователь EFF и руководитель проекта DES Challenge, и Пол Кочер, основатель компании Cryptography Research.
Процессор EFF DES Cracker
Разработанная ими система смогла успешно подобрать ключ к зашифрованному образцу методом простого перебора всего за 56 часов, то есть менее чем за трое суток. Для этого DES Cracker потребовалось проверить около четверти всех возможных комбинаций, а это значит, что даже при самом неблагоприятном стечении обстоятельств на взлом уйдет около 224 часов, то есть не более 10 суток. При этом стоимость суперкомпьютера, с учетом затраченных на его проектирование средств, составила всего 250 тысяч долларов. Нетрудно догадаться, что сегодня взломать подобный шифр еще проще и дешевле: мало того, что железо стало куда мощнее, так еще и благодаря развитию интернет-технологий хакеру вовсе не обязательно покупать или арендовать необходимое оборудование — вполне достаточно создать ботнет из зараженных вирусом ПК.
Данный эксперимент наглядно продемонстрировал, насколько DES морально устарел. А поскольку на тот момент алгоритм использовался в составе практически 50% решений в области шифрования данных (по оценке все той же EFF), вопрос о поиске альтернативы встал как никогда остро.
Новые вызовы — новый конкурс
Справедливости ради стоит сказать, что поиски замены для Data Encryption Standard начались практически одновременно с подготовкой EFF DES Cracker: Национальный институт стандартов и технологий (NIST) США еще в 1997 году объявил о запуске конкурса алгоритмов шифрования, призванного выявить новый «золотой стандарт» криптобезопасности. И если в былые времена аналогичное мероприятие проводилось исключительно «для своих», то, памятуя о неудачном опыте 30-летней давности, в NIST решили сделать конкурс полностью открытым: в нем могли принять участие любая компания и любое частное лицо, независимо от места дислокации или гражданства.
Такой подход оправдал себя еще на этапе отбора претендентов: среди авторов, подавших заявку на участие в конкурсе Advanced Encryption Standard, оказались и всемирно известные криптологи (Росс Андерсон, Эли Бихам, Ларс Кнудсен), и небольшие IT-компании, специализирующиеся на кибербезопасности (Counterpane), и крупные корпорации (немецкая Deutsche Telekom), и образовательные учреждения (Лёвенский католический университет, Бельгия), а также стартапы и небольшие фирмы, о которых мало кто слышал за пределами их стран (например, Tecnologia Apropriada Internacional из Коста-Рики).
Интересно, что в этот раз в NIST утвердили всего два основных требования к алгоритмам-участникам:
Прием заявок на конкурс Advanced Encryption Standard продлился полтора года. Всего в нем приняли участие 15 алгоритмов:
В случае с «богом войны» эксперты отметили идентичность процедуры шифрования и дешифровки данных, однако этим его преимущества и ограничились. Алгоритм IBM вышел на удивление прожорливым, что делало его неподходящим для работы в условиях ограниченных ресурсов. Наблюдались проблемы и с распараллеливанием вычислений. Для эффективной работы MARS нуждался в аппаратной поддержке 32-битного умножения и вращения на переменное число бит, что опять же накладывало ограничения на перечень поддерживаемых платформ.
MARS также оказался достаточно уязвим к атакам по времени и энергопотреблению, имел проблемы с расширением ключей «на лету», а его чрезмерная сложность затрудняла анализ архитектуры и создавала дополнительные проблемы на этапе практической реализации. Одним словом, на фоне других финалистов MARS выглядел настоящим аутсайдером.
Алгоритм унаследовал часть преобразований от своего предшественника, RC5, тщательно исследованного ранее, что в сочетании с простой и наглядной структурой делало его полностью прозрачным для экспертов и исключало наличие «закладок». К тому же RC6 демонстрировал рекордные скорости обработки данных на 32-битных платформах, а процедуры шифрования и дешифровки были реализованы в нем абсолютно идентично.
Однако алгоритм имел те же проблемы, что и упомянутый выше MARS: тут и уязвимость к атакам по сторонним каналам, и зависимость производительности от поддержки 32-битных операций, а также проблемы с параллельными вычислениями, расширением ключей и требовательность к аппаратным ресурсам. В связи с этим на роль победителя он никак не годился.
Twofish
Twofish оказался довольно шустрым и хорошо оптимизированным для работы на маломощных устройствах, отлично справлялся с расширением ключей и предполагал несколько вариантов реализации, что позволяло тонко адаптировать его под конкретные задачи. В то же время «две рыбки» оказались уязвимы к атакам по сторонним каналам (в частности, по времени и потребляемой мощности), не особо дружили с многопроцессорными системами и отличались чрезмерной сложностью, что, кстати, сказалось и на скорости расширения ключа.
Serpent
Алгоритм имел простую и понятную структуру, что существенно упрощало его аудит, был не особо требователен к мощностям аппаратной платформы, имел поддержку расширения ключей «на лету» и сравнительно легко поддавался модификации, чем выгодно отличался от своих оппонентов. Несмотря на это, Serpent был в принципе самым медленным из финалистов, к тому же процедуры шифровки и дешифровки информации в нем кардинально отличались и требовали принципиально разных подходов к реализации.
