28.06 // Увеличение размера ключа в шифрах за счёт использования каскадов

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

С формальной точки зрения блочный шифр с ключевым пространством {0,1}^k, пространством сообщений {0,1}ⁿ является всего лишь эффективно вычислимой (и обратимой) перестановкой E_k на множестве n-битовых строк, заданной k-битовым индексом ключа k, что часто описывается как (k, n)-блочный шифр. Например, n = 64 и k = 56 для DES и n = 128 и k ∈ {128, 192, 256} для AES.

В большинстве приложений, которые используют блочный шифр, как базовый примитив, подразумевается (и требуется), что он представляет собой псевдослучайную перестановку (pseudorandom permutation — PRP), т.е. при использовании случайного секретного ключа он не может быть эффективно различим от случайной перестановки с равномерным распределением. Для того, чтобы зафиксировать определение этой идеи, уровень PRP-безопасности блочного шифра определяется сложностью, требуемой для его различения от случайной перестановки с пренебрежимо малым преимуществом.

Увеличение длины ключа

Длина ключа k является критически важным параметром безопасности для любого блочного шифра E. Атакующий, имеющий в распоряжении некоторое количество пар открытого и шифртекста, может легко получить секретный ключ, используя атаку перебора грубой силой, если он способен выполнить приблизительно 2^k вычислений E. Такая атака восстановления ключа может быть также трансформирована в атаку нахождения PRP-различителя, включающую предел вычислений 2^k, ограничивающий PRP-безопасность любого блочного шифра. Это представляет проблему для существующих блочных шифров с малым размером ключа k для которого 2^k операций не могут больше находиться за пределами доступных потенциальному атакующему вычислительных мощностей.

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

По вышеприведённым причинам, существует практическая потребность в трансформировании любого (k, n)-блочного шифра E в (k', n)-блочный шифр C^E, путём увеличения как размера ключа (т.е. k' > k), так и связанной с этим общей неспецифической безопасности (т.е. PRP-безопасность C^E должна быть существенно выше, чем 2^k, подразумевая, что E сам по себе не содержит никаких специфических уязвимостей). Это известно под названием проблемы увеличения размера ключа блочных шифров и понимание этого требует анализа множества способов конструкций каскадирования. Вместо DES следует рассмотреть неспецифические конструкции, применимые к любому блочному шифру, чтобы получить результаты, полезные в теоретическом плане.

Модель идеального шифра

Чтобы достичь уровня безопасности, обеспечиваемого самими конструкциями увеличения размера ключа, подразумевается, что в базовом блочном шифре нет никаких уязвимостей и он может быть смоделирован с помощью идеального блочного шифра E, предоставляющего независимые равномерные случайно распределённые перестановки для каждого из ключей. Следует ввести определение различителя (distinguisher) D, позволяющее два типа запросов:

• запросы к блочному шифру для изучения функции блочного шифра E для любого ключа и для любого входящего блока (как в направлении шифрования, так и расшифрования).
• запросы к конструкции для изучения её как конструкции увеличения длины ключа C^E_K, использующей блочный шифр E и равномерно распределённый случайный секретный k'-битовый ключ K'; так и запросы к равномерно распределённой случайной перестановке P, независимой от E (опять же, с возможностью запросов в обоих направлениях).

Таким образом, различитель взаимодействует с комбинацией систем ( E, C^E_K' ) или с (E, P) и его целью является определение, в какой из двух ситуаций он находится. Сложность определяется суммой его запросов обоего типа, что позволяет вывести результат в информационно-теоретической форме. Отметим, что безопасность любой схемы увеличения длины ключа в этой модели ограничены предельным значением сверху 2^k+n, что соответствует тривиальной атаке запросов к блочному шифру и самой конструкции.

Некоторые типы каскадов

Самым очевидным способом построения конструкции, решающей проблему увеличения длины ключа, является простое повторение блочного шифра много раз с использованием независимых ключей на каждом шаге — решение известное как каскадирование. Его безопасность являлась предметом множества обширных исследований в различных моделях, включая информационно-теоретическую модель идеального шифра, описанную выше. Широко известно, что каскады с удвоением слабо увеличивают безопасность из-за атак встречи посредине так, что безопасность возрастает в определениях преимущества в нахождении различителя лишь на уровне достижимых параметров сложности атаки. Существенным увеличением безопасности является самый короткий тройной каскад, что послужило принятию стандарта Triple-DES (3DES). На основе ключей k₁, k₂, k₃ ∈ {0,1}⁵⁶, 3DES шифрует 64-битное сообщение m:

3DES был формально изучен Беллейром и Рогавеем, показав безопасность примерно 2^k+min{k,n}/2 запросов при замене DES на идеальный блочный шифр. Гези и Маурер показали, что нижний порог безопасности в дальнейшем растёт с ростом каскада для блочного шифра при k ≤ n, достигая приблизительно 2^{min{(2lk)/(l+1),k+n/2}} запросов для нечётного каскада длиной l; с увеличением l эта величина достигает 2^{min{2k,k+n/2}}. Впоследствии, как было показано Ли безопасность каскада достигает 2^k+min{k,n}, но такое приближение становится актуальным только при очень большом росте размера каскада (l ≥ 16). С другой стороны Люкс продемонстрировал, что лучшая атака на тройное шифрование в модели идеального шифра потребует 2^k+n/2 запросов.

Альтернативным подходом к проблеме увеличения ключа является техника, основанная на отбеливании ключа, впервые выполненная Райвистом в DESX. В ней вход и выход шифра маскируются ("отбеливаются") операцией XOR с дополнительным ключевым материалом следующим образом: с помощью тройки ключей (k_i, k_o, k) ∈ ( {0,1}⁶⁴ )² x {0,1}⁵⁶ сообщение m отображается в:

Обобщение DESX на случай произвольных k,n показано в работах Килиана и Роговея и составляет 2^(k+n)/2 даже если для обоих обеливающих шагов использовать один и тот же ключ.

В попытке комбинирования каскадов и ключевого отбеливания Гази и Тессаро предложили т.н. 2-XOR каскад (или рэндомизированную каскадную конструкцию). Она состоит из каскада длиной 2, перемежающегося двумя отбеливающими шагами, отображающими каждое n-битовое сообщение m ключом (k, z) ∈ {0,1}^k x {0,1}ⁿ:

где k^~ выводится из k детерминированным способом (например инвертированием единственного определённого бита). Авторами было доказано, что 2-XOR каскад безопасен до 2^k+n/2 запросов и также показано, что этот предел является достаточно точным. Последующая независимая работа Ли рассматривает обобщённый случай XOR-каскада длиной l (с независимыми ключами и XOR-шагом в конце) и показывает, что его свойства безопасности приближаются к оптимальному пределу 2^k+n, но опять же только при больших значениях l.

Помимо перечисленных наиболее известных работ, существует огромное количество исследований по каскадным конструкциям в разных моделях безопасности, как информационно-теоретической^*, так и вычислительной. Модели из разных работ часто ортогональны друг другу и трудно сравнимы между собой.

Автор исследования "Plain versus Randomized Cascading-Based Key-Length Extension for Block Ciphers", Peter Gazi, кафедра компьютерных наук Швейцарской высшей технической школы Цюриха, рассматривает семейство различных конструкций каскадов, в т.ч. l-каскады, l-XOR-каскады и последовательные конструкции, включающие в себя т.н. KAC — Key Alternating Cipher. KAC — это каскад из XOR независимых ключей, модифицирующих публично известную перестановку. В упрощённо-идеализированном виде, если считать раундовую функцию блочного шифра идеальной перестановкой, то, например шифр AES укладывается в конструкцию KAC.

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

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

^* Информационно-теоретической моделью в терминологии автора являются модели случайного оракула или идеального блочного шифра, которые используются для доказательства стойкости криптопримитивов, которые заведомо не являются информационно-теоретически стойкими на основе сравнительного анализа (сравнение IT-стойкой идеальной и выч.-стойкой реальной модели). Вычислительная модель (у других авторов "стандартная модель") используется для более непосредственного исследования.

Источник: Cryptology ePrint Archive