Введение в криптографию: симметричное шифрование

Введение в криптографию: симметричное шифрование

valekas

12.08.2020

симметричное шифрование

Мир компьютерных наук может вселять страх, особенно если пытаться разобраться в нём самостоятельно. Поэтому я решил написать обзор основ криптографии для тех, кто хотел бы в неё углубиться, но не знает, с чего начать. В основу обзора лёг курс криптографии от преподавателя Стэнфордского университета Дэна Бонеха, доступный на Coursera.

Я решил пройти этот курс, так как я блокчейн-разработчик без традиционного образования в области компьютерных наук. В университете я изучал экономику, но затем ушёл в компьютерное программирование. Начав программировать, я стремился «стать ближе к компьютеру» – разобраться, что скрывается под всей той абстракцией, с которой я имел дело, занимаясь веб-разработкой. Переход с веб-программирования на криптовалюту и распределённые системы был безумно увлекательным, в том числе благодаря углублению в криптографию. Однако мне нужен был более прочный фундамент. Поскольку это довольно обширная область, я не пожалел $70, чтобы получать информацию на форуме, который модерируют преподаватели Стэнфордского университета. Но курс можно пройти и бесплатно без проверки заданий преподавателями.

Итак, приступим.

Что такое криптография?

В сущности, криптография – это практика безопасного общения при наличии потенциальных сторонних недоброжелателей. Понятие безопасного общения подразумевает две основных составляющих:

  1. Защита от перехвата: конфиденциальность данных.
  2. Защита от манипуляции данными: целостность информации, что означает, что никто не может изменить отправляемые вами данные, заставив получателя принять искажённые данные за действительные.

Конфиденциальность данных достигается с помощью шифрования, которое может принимать две формы: симметричную и асимметричную.

  • Симметричное шифрование использует единственный ключ, которым должны обмениваться все участники коммуникации.
  • Асимметричное шифрование использует личные ключи. У каждого участника есть пара из открытого и закрытого ключей для шифрования и дешифрования сообщений.

В настоящей статье мы сосредоточимся на симметричном шифровании.

Два типа шифров

Шифрование обеспечивает конфиденциальность данных и включает две важных составляющих:

  1. Секретный ключ: в контексте симметричного шифрования можно предположить, что у наших участников Алисы и Боба есть общий секретный ключ.
  2. Шифр: алгоритмы шифрования и дешифрования.

Важно отметить, что алгоритмы шифрования и дешифрования известны всем. В секрете хранится лишь ключ.

Есть два типа симметричных шифров: потоковые и блочные. Для надлежащего понимания этих шифров будет полезно знакомство с битовыми операциями (операциями, выполняемыми над битами), в частности с исключающим «или» (XOR). Если вкратце, то это сложение двух битов, при котором, если они разные (0 и 1), результат равен 1, а если они одинаковые (два нуля или две единицы), результат равен 0. В дальнейшем изложении предполагается, что читатель знает, что такое XOR и что эту операцию принято обозначать знаком ⊕.

Потоковый шифр

Потоковый шифр – это такой симметричный шифр, где над открытым (исходным) текстом (в байтовом виде) при шифровании побитово выполняется операция XOR с помощью ключа (также в байтовом виде). Тот же процесс используется для расшифровки. Учитывая характер операции XOR, если мы проделаем её над зашифрованным текстом (шифротекстом) с помощью ключа, получим исходный открытый текст.

потоковый шифр
Как устроен потоковый шифр. Источник: Дэн Бонех

Внимательные читатели, наверное, догадались, что у ключа и открытого текста должно быть что-то общее, причём очень важное. Верно! Ключ и открытый текст должны быть одинаковой длины. Это, конечно, не очень практично.

Чтобы сделать потоковый шифр более практичным, используются генераторы псевдослучайных чисел. Генератор псевдослучайных чисел – это детерминированная процедура, которая на основе входа выдаёт более длинный псевдослучайный результат. «Детерминированная» означает, что эта процедура при одинаковом входе всегда выдаёт один и тот же выход (т. е. «abc123» всегда даёт «8474f24e0d72e1b949ffd2…»). Слово «псевдослучайный» означает, что хотя выход на самом деле не случайный (поскольку он детерминирован на основе конкретного входа), он неотличим от настоящей случайной строки. Другими словами, если иметь набор входов и выходов, то невозможно понять, какому выходу соответствует какой вход. Если использовать в качестве входа общий секретный ключ, можно получить более длинный псевдослучайный ключ, с помощью которого будет проведена операция XOR над открытым текстом такой же длины.

Описанная реализация потокового шифра называется «одноразовый блокнот». Очень важное её свойство заключается в том, что ключ можно использовать только ОДИН РАЗ. Если он используется повторно, безопасность сообщений скомпрометирована.

Ниже показан слайд из курса. PRG(K) обозначает псевдослучайную последовательность, сгенерированную из нашего общего ключа K. Символ ⊕ обозначает операцию XOR; C – шифротекст; m – сообщение (открытый текст).

Источник: Дэн Бонех

В сущности, слайд показывает, что если использовать ключ дважды, то можно провести операцию XOR над двумя шифротекстами, что будет равно операции XOR над двумя открытыми текстами. Поскольку в понятном человеку языке много избыточности, смышлёный злоумышленник с помощью этой информации сможет полностью восстановить сообщения.

Чтобы не повторять ключ одноразового блокнота, но сохранить один общий секретный ключ, применяется концепция нонсаНонс – это произвольное число, которое в криптографической коммуникации может использоваться только один раз. Вместе с шифротекстом можно также отправлять нонс, который будет слагаться с секретным ключом, чтобы при каждом шифровании давать другой псевдослучайный ключ.

(Возможно, вы обратили внимание, что на слайде выше написано «атака 1». Если у вас возник вопрос об «атаке 2», то она относится к тому факту, что потоковый шифр обеспечивает конфиденциальность, но НЕ целостность данных, упоминавшуюся в начале статьи).

Блочный шифр

Второй тип шифров – блочные. Блочный шифр использует вход фиксированной длины и циклически снова и снова шифрует исходный текст, используя каждый раз другой ключ («раундовый ключ»), пока не выдаст шифротекст той же длины. 3DES и AES – два примера блочных шифров, которые соответственно используют вход из 48 и 128 битов.

схема блочный шифр
Схема блочного шифра. Источник: Дэн Бонех

На слайде выше показана базовая архитектура блочного шифра. Как можно видеть, для получения в каждом раунде нового ключа используется алгоритм расширения ключа. Исходный текст (m) шифруется снова и снова, пока не будет получен шифротекст (C) такой же длины.

Ради краткости в этой статье я буду рассматривать AES. Несмотря на историческую значимость DES/3DES, AES сегодня более широко применяется.

схема блочный шифр
Источник: Дэн Бонех

AES построен как подстановочно-перестановочная сеть (SP-сеть). AES использует блоки размером 128 битов, что равно 16 байтам. 16 байтов записываются как матрица 4 на 4. Такая матрица удобна для операций с данными. В каждом раунде процесс следующий:

  1. Проводим операцию XOR над исходным сообщением и первым раундовым ключом (k0).
  2. Выполняем подстановку, заменяя блоки данных другими на основе определённой таблицы (процедура ByteSub).
  3. Проводим перестановку, сдвигая и перемешивая биты (процедуры ShiftRow и MixColumn).
  4. Процесс повторяется 10 раундов.

В последнем раунде опускается процедура MixColumn, проводится операция XOR с последним раундовым ключом и получаем итоговый шифротекст. Для расшифровки используется обратный процесс. Тем, кто желает углубиться, могу посоветовать ознакомиться с сетью Фейстеля, которая используется в 3DES, чтобы сравнить разные блочные шифры.

После запуска архитектуры Westmere компания Intel стала встраивать в свои процессоры специальные инструкции для оптимизации AES, и вскоре за ней последовала AMD.

Режимы блочного шифрования

В отличие от потоковых, блочные шифры используют вход фиксированной длины. Очевидно, мы хотим одновременно обрабатывать больше 16 байтов данных. Поэтому дальше важно понять режимы, в которых можно применять блочные шифры к большим объёмам данных. Первый из них – режим электронной кодовой книги (ECB). ECB просто разбивает данные на блоки по 16 байтов и выполняет AES-шифрование единообразно. Это можно делать параллельно и очень быстро. Однако это не слишком безопасно.

схема блочного шифра
Источник: Дэн Бонех

Причина в том, что если 16-байтовые сообщения повторяются, шифротекст тоже будет повторяться. Так потенциальный злоумышленник сможет получить информацию о наших данных. Можно показать эту уязвимость на примере изображения, зашифрованного посредством ECB. На картинке ниже видно, что тёмные волосы и футболка позволяют различить очертания, по которым можно понять, что зашифрован снимок чьего-то лица.

Источник: Дэн Бонех, B. Preneel

Важно, чтобы схемы шифрования были семантически стойкимиСемантическая стойкость означает, что, если есть шифротекст, соответствующий одному из двух открытых текстов, недоброжелатель не может знать с вероятностью больше 1/2, какому именно открытому тексту он соответствует. Очевидно, что режим ECB семантически нестойкий. Зашифрованное изображение выдаёт много информации, позволяющей догадаться об исходнике.

ECB – это пример режима с одноразовым ключом (то есть, как и в случае одноразового блокнота, ключ нельзя использовать повторно). Ещё один, более безопасный режим с одноразовым ключом – детерминированный режим счётчика. Можете поискать о нём информацию самостоятельно, а я перейду к безопасным режимам с многоразовыми ключами.

В режиме сцепления блоков шифротекста (CBC) каждый 16-байтовый блок открытого текста складывается посредством операции XOR с шифротекстом предыдущего блока, после чего выполняется блочное шифрование (AES).

Источник: Дэн Бонех

Начинаем со случайного вектора инициализации (IV), то есть начального значения в циклическом процессе. В случае CBC значение IV должно быть случайным (и, следовательно, непредсказуемым), а значит, уникальным в каждой транзакции. Первый блок шифротекста – это просто незашифрованный случайный IV. Чтобы получить остальной шифротекст, сначала проводится операция XOR над случайным IV и первым блоком открытого текста (m[0]). Результат шифруется с помощью раундового ключа k, и получаем первый зашифрованный блок шифротекста (c[0]). Далее проводится операция XOR над этим шифротекстом и следующим блоком открытого текста (m[1]), результат шифруется раундовым ключом k, и получаем следующий блок шифротекста (c[1]). Процесс продолжается, пока не будут зашифрованы все блоки.

Источник: Дэн Бонех

Для расшифровки применяется обратный процесс.

Важная составляющая CBC-шифрования – это непредсказуемый случайный IV. Если IV будет предсказуемым, то наша схема шифрования станет уязвимой к атаке на основе подобранного открытого текстаАтака на основе подобранного открытого текста (CPA) подразумевает, что злоумышленник может получить шифротексты произвольных открытых текстов и с их помощью раскрыть информацию о зашифрованных сообщениях. Следовательно, непредсказуемый IV обеспечивает защиту от CPA.

Попробую объяснить, как может выглядеть такая атака. Провести CPA при наличии предсказуемого IV можно из-за свойств XOR. Результат операции XOR над двумя одинаковыми значениями (например, 0101 ⊕ 0101) всегда будет равен нулю. Поэтому, если вы подозреваете, что шифротекст c[0] соответствует определённому открытому тексту m[0], можно проверить гипотезу с помощью предсказуемого IV. Если открытый текст зашифровали с помощью IV1 (c[0] = E(k, m[0] ⊕ IV1)), то можно зашифровать новый открытый текст и посмотреть, совпадёт ли результат с c[0]. Поскольку можно предсказать, что IV будет IV2, вы проделываете m[0] ⊕ IV1 ⊕ IV2. CBC проделает операцию XOR над этим входом и следующим IV (IV2): c[1] = E(k, m[0] ⊕ IV1 ⊕ IV2 ⊕ IV2). Следовательно, два IV2 взаимно уничтожаются, и мы снова шифруем E(k, IV1 ⊕ m[0]), что, опять же, даст c[0], и в таком случае мы можем догадаться, что было ранее зашифровано с помощью IV1.

Наконец, хотелось бы рассмотреть ещё один режим блочного шифрования: рандомизированный режим счётчика (CTR). Это последний, самый безопасный режим, и он также более эффективен, чем CBC.

Источник: Дэн Бонех

Рандомизированный режим счётчика также использует случайный IV, но здесь он служит другой цели. Наш ключ складывается (например, посредством AES) с итерированной версией нашего IV: например, в каждой итерации можно увеличивать IV на единицу, чтобы результат не повторялся. Мы делаем это, пока не получим ключ такой же длины, как наш открытый текст. Теперь, как и в случае потокового шифра с одноразовым ключом, мы проводим операцию XOR над нашим открытым текстом и псевдослучайным ключом, чтобы получить шифротекст. Если у вашего компьютера есть несколько AES-процессоров, то это очень эффективно, так как может выполняться параллельно. В CBC каждый шифротекст зависит от предыдущего блока, поэтому вычислять его параллельно невозможно.

Чтобы получить псевдослучайный ключ из сложения IV и нашего секретного ключа, блочный шифр не обязателен. Блочные шифры должны быть обратимы. Если внимательно рассмотреть механизм рандомизированного режима счётчика, то можно заметить, что для дешифровки не нужно выполнять в обратном порядке F(k, IV). Учитывая свойства XOR, достаточно взять тот же псевдослучайный ключ и сложить его посредством XOR с нашим шифротекстом. То есть для дешифровки нужно повторить операцию, а не провести её в обратном порядке.

Если выражаться абстрактно (до сих пор я избегал абстрактных понятий), это значит, что процедура, которую мы используем для сложения нашего секретного ключа и IV (F(k, IV)) должна быть псевдослучайной функцией (PRF), а не псевдослучайной перестановкой (PRP). На самом деле мы сталкивались с этими концепциями в этой статье. И PRF, и PRP – это детерминированные процедуры, которые при конкретном входе дают псевдослучайный выход (AES, XOR). Однако PRP имеет строгое требование обратимости. Собственно говоря, понятия PRP и блочный шифр (например, AES) часто используются как синонимы. Но PRF НЕ должна быть обратимой.

Итак, на этом заканчивается наш обзор симметричного шифрования. Мы рассмотрели потоковые и блочные шифры. Затем, поскольку блочные шифры одновременно способны обрабатывать лишь 16 байтов, мы поговорили о режимах их применения к большим открытым текстам. Наконец, мы также объяснили разницу между PRP и PRF.

Источник