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

Итак, если каждый раз пересогласовывать ключ вы не хотите, преобразование ключа re-keying спешит вам на помощь! Re-keying – подход, основная идея которого заключается в следующем: непосредственная обработка данных производится с помощью последовательности ключей, получаемых из первоначально согласованного ключа (будем называть его начальным) путем применения специально подобранных детерминированных преобразований. Эти преобразования позволяют считать выработанные ключи "почти" случайными и независимыми.

Будем выделять два типа подходов к re-keying: external (внешний) и internal (внутренний). Рассмотрим каждый из них подробно.

Internal re-keying

Подход internal re-keying заключается в модификации какого-то конкретного режима работы блочного шифра таким образом, чтобы ключ, с помощью которого происходит непосредственное преобразование данных, периодически изменялся по ходу обработки одного сообщения. Применение подхода internal re-keying приводит к изменению порядка обработки "единицы" работы режима. Таким образом, данный подход не предполагает рассмотрение режима работы шифра как черного ящика, а затрагивает внутренние особенности его строения (отсюда термин "internal"). В результате применения подхода internal re-keying образуется новый класс расширенных режимов с внутренним преобразованием ключа (internally re-keyed mode of operation), причем конкретный вид преобразования зависит от используемого базового режима. Пожалуй, первый режим работы блочного шифра с использованием internal re-keying был описан в документе RFC 4357, хотя в то время такого понятия как internal re-keying не существовало, как и открытых работ, посвященных исследованию криптографических свойств описанных режимов.

Понятие "internal re-keying" неразделимо с понятием "секция". Секция – это подстрока сообщения, обрабатываемая на одном ключе до его преобразования, при этом такой ключ будем называть секционным. Размер секции является параметром расширенного режима работы шифра. Он должен фиксироваться с учетом требований к уровню стойкости и эффективности. Сложность выбора состоит в сохранении баланса: чем чаще меняется ключ по ходу обработки одного сообщения, тем выше уровень стойкости, но меньше скорость.

Основную идею механизма internal re-keying можно проиллюстрировать следующим образом:

Здесь каждое отдельное сообщение делится на секции длины N блоков каждая. Первая секция каждого сообщения обрабатывается на начальном ключе K. Перед обработкой каждой следующей секции текущий секционный ключ преобразуется по некоторому определенному алгоритму. 

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

С основной идеей internal re-keying мы ознакомились. Но действительно ли он решает поставленную нами выше проблему эффективной и "безопасной" обработки большого количества данных?

Сравним некоторый расширенный режим с его режимом-прообразом — тем же режимом, но без использования internal re-keying, на предмет ограничений по нагрузке на ключ. 

Для начала рассмотрим режим-прообраз. Предположим, что допустимая нагрузка на ключ L1, соответствующая ограничениям по побочным каналам, позволяет обрабатывать q сообщений длины m1 блоков. В то же время допустимая нагрузка на ключ L2, соответствующая комбинаторным ограничениям, при том же количестве сообщений q позволяет обрабатывать сообщения длины m2. Таким образом, для режима-прообраза итоговая допустимая нагрузка на ключ соответствует самому строгому из ограничений L1, а максимальная длина сообщения равна m1.

Теперь рассмотрим расширенный режим с внутренним преобразованием ключа.

Информация, получаемая по побочным каналам, имеет отношение только к ключу, на котором непосредственно обрабатывается сообщение. Если используется такой алгоритм преобразования ключа, что секционные ключи для противника являются "почти" случайными и независимыми, то каждое изменение ключа приводит к тому, что информация о предыдущем ключе к противнику больше не поступает. Поэтому, выбрав размер секции N таким образом, что q • N ≤ L1, можно больше не думать об ограничениях по побочным каналам и сфокусироваться только на комбинаторных ограничениях. Как правило, комбинаторные свойства новых режимов с использованием подхода internal re-keying только улучшаются, что должно подтверждаться строгими доказательствами (см., к примеру, [1]). Следовательно, при том же уровне стойкости новая допустимая нагрузка на ключ L2’, соответствующая комбинаторным ограничениям, в разы увеличивается в сравнении со старой допустимой нагрузкой L2.

Для наглядности рассмотрим пример. Пусть для некоторого режима-прообраза в протоколе P зафиксированы следующие нагрузки на ключ: L1 = 128 МБ, L2 = 1 ТБ. Тогда, если мы хотим обработать, к примеру, 128 сообщений, их длина не должна превышать L1/128 = 1 МБ. Если же расширить этот режим с помощью internal re-keying с размером секции N = 1 МБ, то при том же общем числе сообщений длина каждого сообщения может быть увеличена до нескольких терабайтов.

Но что же это за «определенный алгоритм», по которому преобразуется ключ? Как уже было сказано ранее, этот алгоритм зависит от базового режима, поэтому в качестве примера рассмотрим алгоритм преобразования ключа ACPKM ("ACPKM" = "Advanced Cryptographic Prolongation of Key Material"), который применяется к режиму шифрования CTR.

Сообщение разбивается на секции, и в качестве ключа первой секции используется начальный ключ K. Для зашифрования (i+1) секции значение (i+1)-ого секционного ключа вычисляется с помощью i-ого ключа следующим образом (на примере блочного шифра Кузнечик):

Kⁱ⁺¹ = E_Kⁱ(W₁) | E_Kⁱ(W2),

где W₁ и W₂ – некоторые константные строки, а операция "|" – конкатенация. То есть для получения нового ключа достаточно преобразования двух блоков на предыдущем ключе. Согласитесь, это гораздо проще, чем заново согласовывать ключ. 

Таким образом, internal re-keying позволяет в разы увеличить допустимую нагрузку на ключ, практически не снижая эффективности.

Internal re-keying более всего подходит для использования в протоколах, где обрабатываются сообщения большого размера, например, CMS-сообщения, так как он позволяет достичь существенный выигрыш именно в длине сообщений, а не в количестве.

Если вас интересует существенное увеличение именно количества сообщений, читайте следующий раздел.

Внешнее преобразование ключа external re-keying

Основным отличием external re-keying от определенного выше подхода internal re-keying является то, что ключ меняется не в процессе обработки одного сообщения, а после обработки некоторого количества целых сообщений. Применение данного подхода не влияет на внутреннее строение режима и не меняет порядка обработки отдельных сообщений – тех самых "единиц" работы режима. То есть external re-keying может рассматриваться в качестве "режима использования режима" (режим с точки зрения external re-keying – это черный ящик). Следствием этого является безусловный плюс данного подхода – конкретные алгоритмы преобразований ключа, применяемые в рамках external re-keying, могут использоваться совместно с любыми режимами работы шифра. Впервые криптографические свойства данных конструкций были исследованы в работе Абдалы и Белларе, в которой совокупность алгоритма преобразования ключа и режима работы шифра в рамках подхода external re-keying рассматривается, как расширенный режим с внешним преобразованием ключа (по аналогии, externally re-keyed mode of operation). Такая точка зрения вполне оправдана – задачи, решаемые классическим и расширенным режимами, одинаковы.

Основную идею механизма external re-keying можно проиллюстрировать следующим образом:

Из начального ключа K по некоторому определённому алгоритму вырабатывается последовательность подключей K^i – ключей, с помощью которых будут непосредственно обрабатываться сообщения. Аналогом понятия "секция" для расширенного режима с внешним преобразованием ключа является количество сообщений, которое можно обрабатывать на одном подключе. Для упрощения понимания будем считать, что каждый из подключей K^i может применяться для обработки максимум h сообщений длины m блоков.

Примечание: выделяют несколько способов получения ключей обработки данных из начального ключа: с мастер-ключом, который никогда не используется непосредственно для обработки данных, и без него, параллельный и последовательный способы. 

По аналогии с подходом internal re-keying убедимся в том, что external re-keying также решает проблему эффективной и "безопасной" обработки большого количества данных.

Ситуацию, при которой мы просто шифруем данные, не пользуясь подходом external re-keying, можно представить на рисунке следующим образом:

Здесь L1 и L2 — допустимые нагрузки, соответствующие ограничениям по побочным каналам и комбинаторным ограничениям соответственно, а q1 и q2 — количества сообщений длины m, которые мы можем безопасно обработать при данных допустимых нагрузках. Таким образом, итоговая допустимая нагрузка на ключ без использования external re-keying равна L1, а обработать мы можем лишь q1 сообщений.

Теперь применим подход external re-keying.

Приведенные выше рассуждения об информации, получаемой по побочным каналам, справедливы и для подхода external re-keying. Поэтому, выбирая параметр h таким образом, что h • m ≤ L1, можно учитывать только допустимую нагрузку L2', соответствующую комбинаторным ограничениям. Согласно все той же работе Абдалы и Беллареа нагрузка L2' в разы увеличивается в сравнении с допустимой нагрузкой L2.

Для наглядности рассмотрим пример. Пусть для некоторого режима в протоколе P зафиксированы следующие нагрузки на ключ: L1 = 128 МБ, L2 = 1 ТБ. Если мы хотим обработать сообщения длины 1 МБ каждое, их количество не должно превышать 128. Если же расширить этот режим с помощью external re-keying, то при той же длине количество сообщений может быть увеличено в десятки тысяч раз.

Так как алгоритмы преобразования ключа, разрабатываемые в рамках подхода external re-keying, могут применяться с любыми режимами работы шифра, мы можем их рассматривать без привязки к последним. Приведем пример конкретного алгоритма получения t ключей обработки из начального ключа K для шифра Кузнечик: 

K¹ | K²... | K^t = E_K([0]) | E_K([1]) | ...|E_K([2t-1]),

где [i] — строка длины 128 бит, которая является двоичным представлением числа i. Таким образом, для получения t ключей надо зашифровать всего лишь 2t констант. 

Преобразование ключа в рамках подхода external re-keying планируется к применению в протоколе TLS 1.3 (к примеру, в процедуре Key Update), который служит для передачи большого числа сообщений небольшой длины. 

В теории все хорошо, а что на практике? 

Итак, мы рассмотрели два подхода re-keying: внутреннее и внешнее преобразования ключа. Так как internal re-keying порождает новый класс режимов шифрования, а external re-keying определяет порядок их использования, выделяется и третий подход, объединяющий в себе достоинства последних. Таким образом, можно прийти к следующей структуре взаимодействия блочного шифра, режимов его работы и подходов к преобразованию ключа: 

Несмотря на то, что понятия external re-keying и internal re-keying сформировались относительно недавно, оба подхода уже давно успешно применяются на практике. Так сложилось, что в зарубежной криптографии практикуют преобразование ключей в рамках подхода external re-keying (например, протокол TLS 1.3), в то время как у нас в стране широко распространено применение расширенных режимов с внутренним преобразованием ключа (internal re-keying). Напомним, что в отечественном варианте протокола TLS 1.0 используется подход internal re-keying, а в разрабатываемой новой версии TLS 1.2 планируется совместное применение двух подходов. Более того, использование подхода internal re-keying совместно с ключевым деревом в качестве механизма external re-keying используется в российской версии протокола IPsec.

Разработка специалистами нашей компании нового поколения расширенных режимов с внутренним преобразованием ключа послужила толчком не только к созданию документа новых методических рекомендаций ТК 26, но и к началу работы над документом, который бы, наконец, ввел понятную классификацию и стал единой базой существующих “безопасных” подходов преобразования ключа. Объединив свои усилия вместе с зарубежными коллегами, мы начали разработку драфта RFC, в котором можно будет найти описание всего спектра механизмов преобразования ключа, а также полезные рекомендации по их применению.

Литература

[1] Akhmetzyanova L.R., Alekseev E.K., Oshkin I.B., Smyshlyaev S.V., Sonina L.A. "On the properties of the CTR encryption mode of the Magma and Kuznyechik block ciphers with re-keying method based on CryptoPro Key Meshing". Матем. вопр. криптогр., 8:2 (2017).

Смышляев С.В., к.ф.-м.н.,

начальник отдела защиты информации

ООО "КРИПТО-ПРО"

Алексеев Е.К., к.ф.-м.н.,

ведущий инженер-аналитик

ООО "КРИПТО-ПРО"

Смышляева Е.С.,

инженер-аналитик 2 категории

ООО "КРИПТО-ПРО"

Мешков Д.А.,

студент 4-го курса

МИЭМ НИУ ВШЭ