id: Гость   вход   регистрация
текущее время 11:08 02/07/2022
Владелец: unknown (создано 28/06/2013 16:36), редакция от 28/06/2013 18:41 (автор: SATtva) Печать
Категории: криптография, алгоритмы, симметричное шифрование
https://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


 
— Гость (01/07/2013 02:46)   <#>
Спасибо за перевод, unknown. Многие высказывания совершенно непонятны (как то «запросы к конструкции»). Нагромаждённые бюрократизмы иностранного языка перемножаются на отсутствие базовых знаний по предмету у читателей, и формулы превращаются в ритуал: вроде что-то и написано, и понятность → 0.

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

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

Модели из разных работ часто ортогональны друг другу и трудно сравнимы между собой.

И после этого они называют криптографию наукой. :-) А если выводы, сделанные по одной модели, будут противоречить выводам, сделанным по другой? Одна, например, будет говорить, что стойкость увеличивается, а другая — что понижается. И что тогда делать?
— unknown (01/07/2013 11:07, исправлен 01/07/2013 11:22)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
В этой статье, как я сумбурно понял, они рассматривают каскады идеальных блочных шифров как ещё одну идеальную конструкцию, не более того.

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


На самом деле, там не такая сложная зависимость по числу идеальных шифров в каскаде. Вид кривой стойкости (неразличимости) примерно одинаков. Спор в доказательствах идёт по поводу строгости оценки приближений и их точности. Для тех кому не нужна сверхоптимизация и строгая теоретическая обоснованность могут подобрать вариант с запасом по худшим оценкам. Но опять же, не для реальных каскадов.



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



Как раз перевод задумывался больше, чтобы ещё раз ввести (ну для самых продвинутых освежить) совершенно базовые понятия — блочный шифр, PRP, ICM. Что ИМХО полезнее, чем частные результаты работы.



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

— unknown (09/01/2014 11:20, исправлен 09/01/2014 11:22)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

В последних работах для тройных и четверных каскадов приведены оценки стойкости 2k+min{k,n/2}. k — размер ключа; n — размер блока. Для данной формулы рассматривались каскады с последовательным шифрованием тремя независимыми ключами (3-DES). Т.е. ближе к 288 бит для идеального DES в составе 3-DES, а не к 2112, как считалось ранее.


Тем самым авторы утверждают, что строгая оценка стойкости 3-DES ими формально доказана только сейчас.


Tight Security Bounds for Triple Encryption. Jooyoung Lee;
Triple and Quadruple Encryption: Bridging the Gaps. Bart Mennink and Bart Preneel.


Отсюда, для тройного AES и пр. шифров с размером ключа и блока 128-бит:


2128+min{128,128/2} = 2192


Для AES-подобных шифров с ключом 256-бит:


2256+min{256,128/2} = 2320


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


Все эти атаки и различители — чисто теоретические. Они м.б. совершенно неприменимы для оценки затрат на расшифровку текстов в реальных ситуациях. Но с точки зрения сертификационного криптоанализа дают некоторое представление о каскадах.

— Гость (14/01/2014 01:55)   <#>

Кстати, этот материал про криптоанализу 3DES ещё не устарел? 112 — до сих пор минимум?

Спасибо за отслеживание актуальных материалов по теме.
— unknown (14/01/2014 09:45)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
То ли интерес к криптоанализу DES ослаб, то ли что ещё, но если не считать комбинированных атак с разменом числа операций на память, считается, что против DES реально эффективен только линейный криптоанализ и вроде никакого прогресса с начала 90-хх как бы нет.
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3