Линейный криптоанализ. Как работает современное шифрование. Часть 1/2
В этой статье поговорим о блочном симметричном шифровании, а также способе взлома — линейном криптоанализе (часть 2). Для исследования реализуем программное обеспечение, наглядно показывающее алгоритм шифрования и его взлом.
В качестве изучаемого шифра возьмем сильно упрощенную версию шифра AES. Шифр AES является одним из самых распространённых алгоритмов симметричного шифрования. На текущий момент этот шифр считается абсолютно стойким. Любой современный процессор поддерживает аппаратное ускорение алгоритма AES.
Для начала, стоит отметить, что этот шифр работает на более низком уровне, чем шифры замены или перестановки, которые работают непосредственно с символами. AES работает с битовыми последовательностями. Для изучения шифра мы используем блок длинной 16 бит, хотя в реальном шифре блок имеет размер 256 бит (что упоминается в названии). Размер ключа равен размеру блока. Соответственно исходный блок можно представить как число от 0 до 65 635 (unsigned int16).
Шифр AES строится на циклической структуре, состоящий из 3-х базовый действий. Действия называют блоками. Рассмотрим внимательнее каждый блок.
S-block
Он же Swap‑block или блок замены. Рассмотрим таблицу для этого блока.
Этот блок принимает на вход блок из 4 бит. Соответственно, исходная последовательность разделяется на 4 блока по 4 бита. Далее происходит замена одного значения на другое.
Блок из 4-х бит может кодировать число от 0 до 15 (всего 16 значений). Представляем входной блок как число (0–15) и прогоняем через S‑block, заменяя значение, согласно таблице замен.
Таблица замены выглядит так:
Например, если блок из 4-х бит кодирует значение 10 (A | 1010), то его значение заменяется на 6 (0110), согласно таблице.
Так через s‑block проходят и заменяются все 4 блока по 4 бита. После этого, они собираются в 1 последовательность из 16 бит и передаются в следующий блок.
Стоит отметить, что это таблицы являются, как правило, открытыми. Они не являются критическими данными для взлома шифра.
P-block
Блок перестановок или permutation‑block.
Верхнее значение относится к конкретному биту и говорит о том, на какое место в выходной последовательности должен быть помещен бит. Например, 1 бит остаётся на своё месте, а 2-й переходит на позицию 5-того бита.
На картинке выше представлен этап прохождения через P‑block. Каждый бит входной последовательности помечен уникальным цветом. Это цвет рамки и местоположение квадратика в одном из углов. Таким образом хорошо видно, куда переходят биты.
Именно этот блок вносит в шифр так называемую нелинейность. Это очень важно для создания стойкого алгоритма.
SP-сеть
Теперь мы готовы целиком построить алгоритм шифрования на основе P и S блоков. Однако, нам понадобится ещё 1 операция, а именно XOR.
Многие с этой операцией и так знакомы, поэтому не будут заострять внимание. Вверху приведена таблица истинности для XOR (Исключающее ИЛИ).
В нашим шифре она используется при «подмешивания» ключа в последовательность бит. Длина блока равна длине ключа, поэтому XOR просто применяется ко всей последовательности сразу.
Рассмотрим схему выше. На ней представлен 1 раунд шифрования. Алгоритм такой:
XOR всей последовательности с ключом
Разделение на 4 блока по 4 бита
Swap‑block
Permutation‑block
Далее следует переход на следующий раунд. Всего 4 раунда. На последнем раунде P‑блок не применяется, но применяется ещё 1 операция XOR.
В реальном шифре AES обычно до 16 раундов. Также стоит отметить, что в AES применяется алгоритм генерации раундовых ключей. т. е. ключ изменяется на каждом раунде, что также значительно усложняет алгоритм. В рассматриваемом нами, учебном шифре, генерация раундовых ключей не применяется для упрощения.
Полученная конструкция из блоков и xor называется SP‑сетью. На её основе работают многие современные симметричные шифры, однако AES является хорошим стандартом. SP‑сеть — это аналог сети Фейстеля. Сеть Фейстеля тоже использует циклическую структуру, но с другими операциями. На основе неё, кстати, работам предыдущий стандарт шифрования — DES.
Далее реализуем программу для нашего шифра. Шифр был упрощен для демонстрации атаки линейного криптоанализа (Во 2 части).
Программная реализация алгоритма
Для программной реализации используется C++ с прикрученными WinForms.
P.S. После написания кода стало ясно, что реализация далека от идеала в плане оптимизации. В программе используются структуры bitset и строки. Это связано с тем, что нужно не только шифровать, но и выводить на экран этапы в +‑ красивом и понятном виде. Уже позже стало ясно, что выгоднее было бы использовать int. Однако, это не делает программу не рабочей и для нашего упрощения и текущей реализации более чем хватает.
Рассмотрим сам алгоритм в общем виде.
void Section::EncryptNoDisplay(KeyGen* keyGen)
{
for (int i = 0; i < this->roundCount; i++) {
string keyStr = keyGen->Generate(this->round);
bitset<16> key(keyStr);
this->XOR(key);
this->Substitution(false);
if (i != 3) {
this->Permutation(false);
}
}
string keyStr = keyGen->Generate(this->round);
bitset<16> key(keyStr);
this->XOR(key);
}Алгоритм на основе описанной выше SP сети. Обратите внимание, что генератор ключей в данном случае каждый раз возвращает одинаковый ключи. В программу закладывалась возможность его генерации, поэтому класс был создан, но для изучаемого шифра является избыточным.
Функция замены выглядит так. Разделяем последовательность на 4 блока и выполняем замены, согласно таблицы замен. Таблица эквивалентна приведенной выше.
unsigned long S_Block::Substitution(bitset<4> input)
{
return this->substitution[input.to_ulong()];
}Ниже представлен код для реализации перестановки битов. Тоже ничего сложного.
unsigned long P_Block::Permutation(bitset<16> input)
{
bitset<16> res;
for (int i = 0; i < 16; i++) {
res[this->permutation[i]] = input[i];
}
return res.to_ulong();
}Параллельно программ выводит весь алгоритм для лучшего его понимания. Пример представлен на рисунке ниже.
В интерфейсе наглядно показана работа SP‑сети и все её шаги. Таким образом можно отследить, какие этапы проходит ваша последовательность при шифровании.
Расшифрование происходит в обратной последовательности и также рисуется справа.
Кнопка «Сгенерировать данные» сгенерирует файл с 1000 парами [значение — зашифрованное значение]. Этот файл нужен для линейного криптоанализа (во 2 части).
В коде (если вы до него доберетесь, конечно) можно будет увидеть подключение с USB порту и передачу туда данных. Не стоит пугаться. Это задумывалась как передача данных на arduino для расширения проекта. Там долго рассказывать. Можете удалить этот код, если он вас смущает.
Полную программную реализацию можно скачать на GitHub. Во 2 части будет описан пример атаки на наш шифр при помощи линейного криптоанализа. Линейный криптоанализ в нашем случае возможен из‑за намеренных упрощений шифра, а именно уменьшение длины ключа, сокращение раундов и отказ от алгоритма генерации раундового ключа.
Другие статьи по теме:
Шифр Виженера
Шифр простой перестановки
