Режимы использования блочных шифров

5.1. Режим электронной кодовой книги (ECB)

Блочные шифры способны работать с блоками небольшой фиксированной длины (64 бита в алгоритме DES, 128 бит в AES и т.д.), но в реальности необходимо шифровать файлы и сообщения произвольной длины.

На первый взгляд решение довольно простое: разбить сообщение на отдельные блоки и зашифровать каждый из них. К сожалению, этот очевидный подход ошибочен.

Самая наглядная проблема состоит в том, что два одинаковых блока открытого текста превращаются в одинаковые блоки шифртекста. Это значит, что противник, имея только зашифрованный текст, может получать некоторую информацию об открытом тексте, следовательно, шифр является небезопасным. Даже если противник не сможет дешифровать эти блоки, он будет знать, что они одинаковые. Например, противник может отслеживать состояние зашифрованного файла на диске и наблюдать, какие его фрагменты остаются неизменными, а какие меняются. Если же размер блока небольшой (например, 64 бита), а открытый текст представляет собой, например, последовательность символов в формате UTF-32 (32 бита на символ), то блочный шифр превращается, по сути, в шифр простой замены – и противник может воспользоваться знаниями о частоте встречаемости биграмм.

Описанный способ носит название электронной кодовой книги и является одним из режимов использования блочных шифров (рис. 5.1).

Рис. 5.1. Режим электронной кодовой книги

Блочный алгоритм шифрования является классическим криптографическим примитивом, который решает одну узкую задачу. Режим использования представляет собой способ применения такого примитива для решения практической задачи. Именно режим определяет, каким образом обрабатывается длинное сообщение, как используются предыдущие блоки, какие дополнительные данные передаются вместе с сообщением и какие свойства безопасности получает итоговая криптографическая система.

Как видно из рассмотренного примера, даже имея надежный алгоритм шифрования, можно все испортить, если пользоваться им неправильно.

Криптографический примитив не решает задачу защиты информации сам по себе. Практическую задачу решает способ его применения

При публикации сведений о защищенном соединении обычно не ограничиваются сообщением о том, что используется, например, алгоритм AES, а указывают более длинную конструкцию – AES-256-GCM или AES-128-CBC. Первая часть названия определяет криптографический примитив (алгоритм шифрования и длину ключа), а вторая указывает режим применения, который во многих случаях оказывает на безопасность системы не меньшее влияние, чем выбор самого алгоритма.

5.2. Режим сцепления шифрованных блоков (CBC)

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

Рис. 5.2. Режим сцепления шифрованных блоков

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

Оба рассмотренных режима требуют, чтобы открытый текст разбивался на блоки длины n. Однако длина открытого текста может быть не кратной n. В этом случае последний блок открытого текста дополняется (padding) до нужной длины.

Отметим свойства режима CBC, вытекающие непосредственно из его схемы. Шифрование строго последовательно: чтобы обработать i-й блок, необходимо дождаться результата для предыдущего, и распараллелить эту операцию невозможно. Дешифрование, напротив, распараллеливается полностью, поскольку для восстановления i-го блока открытого текста достаточно двух блоков шифртекста – i-го и предыдущего. Далее, искажение одного бита шифртекста при передаче портит целиком тот блок открытого текста, которому этот бит принадлежит, и ровно один бит следующего блока; все остальные блоки восстанавливаются верно. В эпоху ненадежных каналов связи подобное самовосстановление считалось достоинством. Сегодня оно скорее вредно: способность получателя принять частично искаженное сообщение и есть та брешь, которой пользуется активный противник.

Наличие дополнения также несет угрозу. Получатель, дешифровав сообщение, обязан проверить корректность дополнения и отбросить его. Если при этом он хоть как-нибудь сообщит противнику, что дополнение оказалось неверным – сообщением об ошибке, кодом ответа или просто разным временем обработки, – противник получит возможность задавать системе вопросы вида «правильно ли расшифровывается вот этот шифртекст». Этого достаточно, чтобы восстановить открытый текст побайтно, вообще не зная ключа. Атаки такого рода (атаки на оракул дополнения) на протяжении многих лет успешно применялись против реальных протоколов.

5.3. Режим обратной связи по выходу (OFB)

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

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

Рис. 5.3. Режим обратной связи по выходу

Превращение блочного шифра в потоковый дает три следствия.

Во-первых, шифрование и дешифрование выполняются одной и той же операцией: гамма складывается с открытым текстом при отправке и с шифртекстом при получении. Это значит, что в основу вместо блочного шифра E может быть положена псевдослучайная функция F(k,m), не имеющая обратной. Во-вторых, длина сообщения перестает быть привязана к размеру блока – для последнего фрагмента берется столько бит гаммы, сколько нужно, и дополнение не требуется. В-третьих, гамму можно выработать заранее, до получения открытого текста, а само шифрование сводится к сложению по модулю 2 и выполняется очень быстро.

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

А вот оценивая, насколько скоро, легко ошибиться. Вероятность того, что очередной блок совпадет с каким-то одним, заранее выбранным, действительно ничтожна и составляет 1/2¹²⁸. Но если вместо блочного шифра используется не имеющая обратной псевдослучайная функция, возможно совпадение любых двух блоков из уже полученных, а число пар растет как квадрат их количества. Это так называемый парадокс дней рождения: совпадение становится вероятным не после 2¹²⁸ блоков, а уже после 2⁶⁴, то есть после корня из общего числа возможных значений. Для 128-битного блока это по-прежнему недостижимо много. Зато для устаревших шифров с 64-битным блоком порог опускается до 2³² блоков, то есть до нескольких десятков гигабайт, и угроза становится вполне практической. Именно поэтому современные стандарты требуют не только уникальности пары <k, IV>, но и ограничивают объем данных, зашифрованных на одном ключе.

Парадокс дней рождения базируется на такой постановке задачи: «Сколько человек должно собраться в одной комнате, чтобы вероятность совпадения дней рождений у двоих из них стала выше 50%?» Интуитивно на этот вопрос обычно отвечают 183 (имея в виду половину дней в году), упуская тот факт, что с каждым новым пришедшим количество возможных вариантов для следующего увеличивается. Правильный ответ – 23, и это сильно ниже ожидаемого.  

5.4. Режим счетчика (CTR)

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

Рис. 5.4. Режим счетчика

Все особенности потокового режима сохраняются. При этом блоки шифрующего потока (гаммы) можно вычислять независимо друг от друга, поэтому выработку можно распараллелить (на четырехъядерном процессоре одновременно шифруются четыре значения счетчика). Аналогично можно дешифровать блоки одновременно и в любом порядке (чтобы дешифровать сотый блок, достаточно вычислить E(K, IV+99)).

В последних двух режимах шифрующая последовательность, очевидно, будет одинаковой, если использовать одну и ту же пару ключ k и инициализационный вектор IV. Перехватив сообщения, зашифрованные такой последовательностью (обозначим ее t), противник может провести операцию сложения шифртекстов по модулю 2:

c₁ ⊕  c₂ = m₁ ⊕  t ⊕  m₂ ⊕  t = m₁ ⊕  m₂

Таким образом, противник будет располагать суммой двух открытых текстов, и, если ему удастся узнать или угадать фрагмент одного из них, второй раскрывается тривиально. Поэтому основное правило использования режимов, основанных на применении инициализационного вектора, гласит: пара <k, IV> должна быть уникальной. Значит, каждое новое сообщение должно шифроваться с использованием нового IV, а объем данных, зашифрованных на одном ключе, приходится ограничивать.

5.5. Основные разновидности криптоанализа симметричных шифров

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

Самой слабой из них является атака только по шифртексту (Ciphertext Only Attack, COA), уже знакомая нам по классическим шифрам: противник располагает лишь перехваченными шифртекстами и не имеет ни одного соответствующего им открытого текста. Именно в этой модели работал частотный анализ. Сегодня стойкость к COA является не достижением, а минимальным требованием: шифр, не устоявший в ней, дальше просто не рассматривается.

Следующей по силе является атака с известным открытым текстом (Known Plaintext Attack, KPA). Предполагается, что противник располагает несколькими парами «открытый текст – соответствующий шифртекст». Такая ситуация возникает достаточно часто. Например, злоумышленник может знать стандартный заголовок документа, типовой шаблон договора или постоянные служебные поля сетевого протокола. Современные алгоритмы шифрования обязаны оставаться стойкими даже при наличии большого количества подобных пар.

Более сильной моделью является атака с избранным открытым текстом (Chosen Plaintext Attack, CPA). Здесь противник получает возможность самостоятельно выбирать сообщения и наблюдать результаты их шифрования. На первый взгляд такая возможность кажется искусственной, однако на практике она встречается весьма часто. Например, злоумышленник может зарегистрировать собственную учетную запись в облачном сервисе, отправлять произвольные запросы защищенному серверу или вынудить устройство зашифровать подготовленные им данные. Современные схемы шифрования проектируются таким образом, чтобы оставаться безопасными и в этой модели.

Наконец, наиболее сильной является атака с избранным шифртекстом (Chosen Ciphertext Attack, CCA). В этой модели противник способен предъявлять получателю произвольные шифртексты и узнавать результат их обработки. Обычно предполагается, что расшифровка именно того сообщения, которое требуется взломать, запрещена, однако любые другие запросы разрешены.

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

Поэтому современные стандарты симметричного шифрования ориентируются именно на стойкость к CCA. Для активного противника недостаточно скрыть содержание сообщения; необходимо исключить возможность использовать механизм дешифрования как инструмент криптоанализа.

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

Существуют также отдельные методы криптоанализа, широко применяющиеся для взлома современных шифров. Перечислим наиболее известные из них.

Статистический криптоанализ. Основан на подсчете частоты встречаемости отдельных символов (или групп символов) в зашифрованном тексте. Подходит для взлома симметричных подстановочных алгоритмов.

Дифференциальный криптоанализ. Разновидность анализа с избранным открытым текстом. Используется при взломе современных симметричных алгоритмов шифрования, в которых текст последовательно проходит несколько раундов преобразований (в частности, известен алгоритм дифференциального криптоанализа шифра DES). Метод основан на прослеживании изменения разности между двумя текстами. Выбирается пара незашифрованных текстов с определенным отличием (X), после чего анализируются отличия, получившиеся после шифрования одним раундом алгоритма, и определяются вероятности различных ключей. Если для многих пар входных значений, имеющих одно и то же отличие Х, при использовании одного и того же подключа одинаковыми (Y) оказываются и отличия соответствующих выходных значений, то можно говорить, что X влечет Y с определенной вероятностью. Эта вероятность и присваивается данному подключу раунда. Затем выбирается подключ с наибольшей вероятностью. Процесс повторяется для всех раундов. Цель – определить таким образом все подключи (сам ключ при этом может остаться неизвестным).

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