id: Гость   вход   регистрация
текущее время 14:34 19/03/2024
Владелец: unknown (создано 28/06/2013 16:36), редакция от 28/06/2013 18:41 (автор: SATtva) Печать
Категории: криптография, алгоритмы, симметричное шифрование
http://www.pgpru.com/Новости/2013/УвеличениеРазмераКлючаВШифрахЗаСчётИспользованияКаскадов
создать
просмотр
редакции
ссылки

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


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


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


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

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


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


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


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

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


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


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

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

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


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


3DESk1, k2, k3 (m) = DESk3 (DESk2 (DESk1 (m)))

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


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


DESXki, ko, k (m) = ko ⊕ DESk (kim)

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


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


2XORk,z (m) = Ek~ ( Ek (mz) ⊕ z)

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


 
Несколько комментариев (5) [показать комментарии/форму]
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3