Улучшенные общие атаки на несбалансированные конструкции Фейстеля расширяющими функциями

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 15:36, 9 августа 2016.
Improved Generic Attacks on Unbalanced Feistel Schemes with Expanding Functions
Авторы Emmanuel Volte[@: 1], Valerie Nachef[@: 2], and Jacques Patarin[@: 3]
Опубликован  ?
Сайт  ?
Перевели Синяков Артем Сергеевич
Год перевода 2015 г.
Скачать оригинал
Аннотация.Несбалансированные конструкции Фейстеля "в общем виде" c расширяющими функциями - это несбалансированные конструкции Фейстеля с истинно случайными внутренними раундовыми функциями от бит в бит, где . С практической точки зрения, у таких конструкций есть интересное свойство: так как и может быть мало (например, 8 бит), зачастую возможно хранить эти истинно случайные функции, чтобы создавать эффективные конструкции (например: CRUNCH, см [1]). Атаки на таких схемы в общем виде были изучены в [2] и [3]. Как указано в [2] и [3], возможностей для таких атак куда больше, чем для сбалансированных конструкций Фейстеля или конструкций со сжимающими функциями. На самом деле, больше количество таких атак затрудняет анализ. В этой статье мы подробно рассмотрим эти атаки. Мы создали компьютерную программу, которая систематически проанализирует все возможные атаки и обнаружит наиболее эффективные. Мы обнаружили условия на внутренние переменные, не рассмотренные достаточно ясно в [3], и мы нашли много новых, улучшенных атак, систематически изучая все "прямоугольные атаки", где , и обобщили эти улучшенные атаки на все k. Многие симуляции наших улучшенных атак были проведены, и они подтверждают теоретический анализ.

Ключевые слова: несбалансированные перестановки Фейстеля, псевдослучайные перестановки, общий вид атак на схемы шифрования, блочные шифры.

Введение

Классический способ построить перестановку из в - использовать конструкцию Фейстеля с раундами с раундовыми функциями . Чтобы получить "Случайную конструкцию Фейстеля", эти раундовые функции должны быть выбраны случайно. "Общие атаки" на эти конструкции - это атаки, которые работают на большую часть этих раундовых функций.

TemplateDifinitionIcon.svg Определение « Определение 1 »
Сбалансированная конструкция Фейстеля - конструкция Фейстеля с и функцией , отображающей из в


Такие конструкции много изучали с времен знаменитой статьи M.Luby и C.Rackoff [4]. Много результатов было получено касаемо безопасности таких классических конструкций Фейстеля (см. [5] для обзора этих результатов). Когда раундов меньше, чем 5, мы знаем атаки меньше чем с операциями, для 5 раундов, атака с операциями дана в [6], и для 3 и 4 раундов атака за дана в [7], [8]. Когда эти функции - перестановки, схожие атаки за 5 раундов даны в [9] и [10]. Таким образом, ради безопасности, рекомендуется использовать как минимум 6 раундов, т.е. каждый бит должен быть изменен хотя бы 3 раза.

TemplateDifinitionIcon.svg Определение « Определение 2 »
Несбалансированная конструкция Фейстеля со сжимающими функциями - конструкция Фейстеля с и функцией , отображающей из в бит.

В [5] M.Naor и O.Reingold обеспечивают безопасность для случаев, когда для первого и последнего раунда используются попарно независимые функции, вместо случайных сжимающих функций. В [11] доказательства безопасности также представлены. В Asiacrypt 2006 ([12]) были изучены общие атаки на такие конструкции.

TemplateDifinitionIcon.svg Определение « Определение 3 »
Несбалансированная конструкция Фейстеля с расширяющими функциями - конструкция Фейстеля с и функцией , отображающей из в бит.

Общие атаки на несбалансированные конструкции Фейстеля с расширяющими функциями - и есть тема этой статьи. Одно преимущество таких конструкций - требуется значительно меньше памяти для хранения случайной функции из в бит, чем случайную функцию из в бит. Несбалансированные конструкции Фейстеля с расширяющими функциями вместе с Xor или случайными перестановками были использованы для создания хэш-функции CRUNCH для соревнования криптографических алгоритмов хеширования, организованные NIST в 2008 ([13]). Наши результаты дают нижнюю границу для количества раундов, используемых в построении хэш-функции. Другие виды конструкций Фейстеля используются для известных блочных шифров. Например, BEAR и LION [14] - два блочных шифра, использующие как сжимающие, так и расширяющие сети Фейстеля. AES-кандидат MARS тоже использует похожую структуру. Атаки на несбалансированные конструкции Фейстеля с расширяющими функциями ранее изучались C.S. Jutla [2], и улучшенные атаки даны в [3]. Тем не менее, некоторые атаки, представленные в <[3] требуют слишком много условий на на внутренние переменные. Эти атаки работают, но со слабыми ключами. В этой статье, мы систематически изучим уравнения между внутренними переменными, чтобы избежать нежелательных коллизий на раундовых функциях. Так мы получим дополнительные условия. Тем не менее, с большим количеством условий, мы покажем, что все еще возможно атаковать такое же количество раундов, как в [3]. В атаках с известным исходным текстом, мы получим ту же сложность, кроме как для , где наша сложность чуть выше, чем в , но у нас не так много условий на внутренние переменные. Для неадаптивных атак с известным исходным текстом, у нас есть общий метод получения CPA-1 из KPA. Тогда мы получим сложности, которые, в большинстве случаев, лучше, чем таковые в [3]. Мы также покажем, что лучшие CPA-1 не получены из лучших KPA. Для , мы сгенерировали все возможные атаки. Мы полагаем, что обобщение этих атак на любые все еще дает наилучшие возможные атаки. Мы также предоставим результаты симуляции для .

Эта статья организована следующим образом. Сначала мы введем нотацию и определения. Потом мы дадим обзор атак. В части 4 мы покажем, как мы сгенерировали все возможные атаки для . В части 5 мы введем разные типы использовавшихся атак. Эти атаки называются TWO, R1, R2, R3 и R4 обобщения атак в [3]. Потом, в части 6, мы представим атаки R1, R2, KPA. В части 7 мы покажем, как получить CPA-1 из KPA. В части 8 мы изучим R1, R2 CPA и предоставим результаты симуляций. Наконец, мы подведем итоги в части 9.

Нотация

Нотация несбалансированных конструкций Фейстеля.

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

Первый раунд показан на рис. 1, ниже:

Feistel 1.png

Получаем:

В более общем случае, можно выразить рекурсивно:

После раундов , вывод может быть выражен через введенные значения :

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

Нотация дифференциальных атак.

Наши атаки используют множества точек. Точки – это пары открытого/зашифрованного текста. Общее количество точек дает нам сложность атаки. Из множества всех точек мы выбираем наборы удаленных точек и подсчитываем, как много наборов длиной подтверждают некоторое равенство(см. рис. 2).

Теперь опишем атаку дифференциальным методом. При использовании этого метода мы можем объяснить, почему количество наборов длиной , которые удовлетворяют условиям, важнее для схем, чем для случайных перестановок. Введем еще одно определение. После раундов определим «горизонтальные равенства» части выхода как и . Допустим . "Вертикальные равенства" части задаются , , . Мы так же дадим определение «дифференциальному равенству» части задающемуся , , . Обратите внимание, что если у нас есть дифференциальные равенства, то чтобы получить горизонтальные равенства, достаточно только первой последовательности равенств, и для вертикальных равенств, достаточно всего лишь первой последовательности. Когда мы накладываем некоторые равенства, мы называем их условиями (они удовлетворяются с вероятностью ). Это может означать, что другие равенства будут удовлетворены с вероятностью, равной единице. В качестве входных и выходных переменных у нас всегда будет дифференциальных условий, а так же горизонтальных или вертикальных условий. На внутренних переменных мы получим горизонтальное или вертикальное равенство, и кроме того наложим больше горизонтальных или вертикальных условий.

Feistel 2.png

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

Теперь приведем пример с атакой на схему. См. Таблицу 1.


Таблица 1. атака
(раунд)
0
1
2
3
4
5
6

Оператор "" в этой таблице обозначает, что имеются горизонтальные равенства или условия.

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


Пример: CPA-1 атаки на Пример: CPA-1 атаки на F 3 6 {\displaystyle F {3}^{6}}

В качестве первого примера, мы приведем новую и более успешную, чем предыдущие, атаку на , которую мы получили. В следующих разделах будет проведен полный анализ для более общих параметров. Эта атака – одна из описанных в таблице 1 с , а так же . Ее иллюстрирует рисунок 3. Он объясняет условия вертикальных и горизонтальных равенств. Условия отображены сплошной линией, а равенства, которые автоматически выполняются – пунктирной.

Мы будет генерировать все возможные сообщения такие, что и первые битов из равны 0. Таким образом, мы генерируем ровно сообщения.

TemplateTheoremIcon.svg Теорема Лемма 1
Входным условиям будут соответствовать наборов точек.
Доказательство
Для первого сообщения существует возможностей. Для второго существует только возможностей, потому что и определяются первым сообщением. Для третьей точки опять существует возможностей, и затем невозможно выбрать последнюю точку. Поэтому четверок точек, удовлетворяют входным условиям.


Для схемы, каждый из этих набора удовлетворит четыре входных условия с вероятностью равной . Таким образом, предполагаемое число четверок точек, которые удовлетворяют, также выходным условиям, будет примерно равно 1. Поскольку существует 5 выходных условий, ожидаемое количество четверок точек, которые удовлетворяют входным и выходным условиям, будет намного ниже для случайной перестановки. Таким образом, эта CPA-1 атака удастся с высокой вероятностью. Мы обнаружили CPA-1 нападение с сложности и сообщений. Это лучше, чем в [3]. Чтобы найти эту сложность можно также использовать таблицу 3 с , , и . Кроме того, мы убедились, что все другие условия метода удовлетворяются (раздел 4), и это нападение было смоделировано с помощью компьютера. Например, с и 1000 атак, мы смогли отличить 575 схем от случайных перестановок, следовательно, процент успеха составляет около 57,5%.

Feistel 3.png

Генерация всех возможных атак для Генерация всех возможных атак для k ≤ 7 {\displaystyle k\leq 7}

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

Чтобы найти атаку нам необходимо сконструировать все возможные(различные) варианты. Существует два ограничения для этих конструкций:

  • Невозможно существование вертикальных условий в одном раунде, т.к. это приводит к коллизии точек, например и .
  • Невозможно существование горизонтальных условий в одном раунде, т.к. это приводит к коллизии точек, например и и .

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

  1. Сложность атаки должна быть меньше, чем общее число возможных сообщений: .
  2. Внутренних условий должно быть меньше, чем выходных: .
  3. Если , то должно быть меньше количества последующих в конце выходных условий. В ином случае легко доказать, что выходные условия полностью эквивалентны внутренним условиям. Так, выходные условия будут появляться не чаще, чем для случайной перестановки.
  4. Количество равенств, использующихся в способе, должно быть меньше количества переменных, включенных в них. Кроме того, мы не рассматриваем равенства, когда переменная встречается лишь один раз для всех равенств. Приведем пример. В разделе 2.2 была приведена атака. Уравнения: , , , . Имеем 4 уравнения и 5 переменных , , , , . Все переменные используются по меньшей мере в двух уравнениях, поэтому мы не можем их упростить.
  5. В равенствах не должно быть узких мест, то есть любое подмножество равенств должно иметь большее число переменных. Если это не так, то атака будет работать только с отдельными функциями (слабые ключи). Этот последний пункт очень сложно осуществить без помощи компьютера.

Наконец, все возможные атаки сортируются в зависимости от их сложности(KPA или CPA-1). Например, существует 71 различная атака на схему и 20 атакCPA-1 со сложность, равной .

Все возможные атаки приведены в полной версии этой статьи. В следующем разделе мы обобщим лучшие атаки(CPA-1 и KPA) для любого при .

Различные виды атак: TWO, R1, R2, R3 и R4

Атаки TWO

Атака TWO заключается в использовании открытых/зашифрованных пар и в подсчете количества пар этих пар, удовлетворяющих отношению входных и выходных переменных. Затем мы сравниваем с , где является количеством пар пар для случайной перестановки вместо . Атака успешна, если мы в состоянии отличить от случайной перестановки, т.е. если разница значительно больше, чем стандартное отклонение и чем стандартное отклонение , где обозначает функцию продолжительности. Эти атаки дают лучшие результаты при раундах от до . Они рассматриваются в [3]. Их сложность резюмируется в разделе 9.

Атаки R1

Здесь мы имеем вертикальные условия на входные и выходные переменные. Эти атаки являются более общими, чем атаки, названные R1 в [3], так как мы допускаем больше вертикальных условий на входные и выходные переменные. Эти атаки были впервые описаны Jutla в [2]. Из нашей дифференциальной нотации мы имеем:

... ... ... ...
Раунд ... ... Раунд ... ...

Таким образом, , , . Здесь обозначает условия на входные переменные. количество вертикальных условий на входные переменные – . обозначает количество условий на внутренние переменные. Мы используем для горизонтальных условий и для вертикальных условий. Аналогично, и обозначают число условий и число вертикальных условий на выходных переменных соответственно. Тогда число раундов определяется . При мы можем легко получить достаточное условие для успеха (без вычисления стандартного отклонения), так как в этом случае для большинства перестановок будет почти в два раза больше решений, чем для случайной перестановки. Таким образом, мы получаем условие: . Во избежание слабых ключей, число уравнений с внутренними переменными должно быть меньше или равно числу внутренних переменных. Это условие не всегда выполняется в [3]. Для R1 атак, легко проверить, что число уравнений задается , а число переменных .Таким образом мы получаем условие: . Сложность такой атаки . Это предполагает, что , т.е. .


Атаки R2

Здесь мы имеем горизонтальные условия на входные и вертикальные условия на выходные переменные. И снова эти атаки носят более общий характер, чем атаки R2 в [3], так как мы допускаем больше горизонтальных условий на входные переменные и больше вертикальных условий на выходные переменные. Имеем:

... ... ... ...
Раунд ... ... Раунд ... ...

Таким образом, , , . Количество горизонтальных условий на входных переменных обозначается . Количество раундов задается как . Условие эквивалентно . Для R2 атак легко проверить, что число уравнений задается , а число переменных . Таким образом мы получаем условие: . Сложность такой атаки . Это предполагает, что , т.е. .

Атаки R3 и R4

Атаки R3 и R4 опишем кратко. Легко получить количество раундов и условия количества уравнений и переменных. Для R3 атак у нас есть вертикальные условия на входных переменных и горизонтальные условия на выходных переменных. Это дает:

... ... ... ...
Раунд ... ... Раунд ... ...

, ,

Для R4 атак мы имеем горизонтальные условия на входных и выходных переменных. Это дает:

... ... ... ...
Раунд ... ... Раунд ... ...

, ,

Лучшие KPA атаки: R1, R2

В этом разделе мы опишем наилучшие найденные атаки. Как упоминалось ранее, для существуют наилучшие атаки. Мы будем описывать в основном один пример R2 атак, так как для каждого раунда есть множество возможных R2 атак, которые дают наилучшие сложности. Можно заметить, что в KPA есть симметрия между R2 и R3 атаками. Таким образом, всегда существуют R2 и R3 атаки одинаковой сложности. Иногда также допустимы R1 атаки. Чаще всего R4 атаки хуже. Мы приводим атаки от раундов до раундов, так как с до раундов TWO атаки обычно лучше и они описаны в [3]. Во всех наших атаках легко проверить(убедиться), что условия, приведенные в предыдущем разделе, удовлетворены. Кроме того, мы всегда ищем атаки, число точек которых минимально. Наши лучшие R2 KPA атаки приведены в таблице 2.

Замечания:

  1. У нас есть следующие R1 атаки:
Таблица 2. Лучшие из известных KPA атаки на для любых
Значение Сложность
(а) При и мы устанавливаем

, ,

Возможно принять , тогда сложность будет равна .

(б) При и мы устанавливаем

, ,

Сложность все еще будет равна , но будет больше .

  1. В [2] Jutla там дал R1 атаку на раунды, но сложность, которую мы получаем здесь с R2 атакой лучше. Можно выполнить атаку R1 на раунды, просто добавив вертикальное условие на входные переменные к атаке на раунды и получаем ту же сложность, которую мы получили бы с R2 атакой. Из-за условий между количеством уравнений и внутренних переменных невозможно использовать этот же метод(идею) для раундов. В этом последнем случае мы используем R2(и, конечно же, R3) атаки.

Способы преобразования KPA атак в CPA-1 атаки

Мы проанализировали все возможные ситуации, и теперь мы в состоянии представить формулы, по которым можно сразу определить сложность CPA в зависимости от начальных условий. Предположим, – количество горизонтальных условий, – количество вертикальных состояний и . Таким образом можно выделить 4 случая:

  1. :
  2. :
  3. :
  4. :
Таблица 3. KPA в CPA
Условия

вертикальные условия

горизонтальные условия

и

горизонтальные условия и вертикальные условия

и

и


Можно заметить, что лучшие CPA-1 атаки не всегда идут от лучших KPA атак. Тем не менее, если мы хотим выразить сложность CPA через KPA, мы можем использовать следующую формулу: .

TemplateTheoremIcon.svg Теорема Теорема 1
Для всех обнаруженных CPA-1 атак лучшим решением будет сохранить первые биты постоянными и генерировать все возможные сообщения с такими же первыми битами.
Доказательство
Продемонстрируем данное доказательство на примере первого случая. Лучшим способом выбрать сообщения является сохранение некоторых битов постоянными (например, равными 0) и рассмотрение всех возможных комбинаций для других разрядов. Мы выберем различных битов из первых бит и различных битов из последних бит. Итак, мы имеем и , и это позволит нам сгенерировать точек (открытых/зашифрованных пар). Теперь мы посчитаем, сколько наборов точек будут подходить по входным условиям. Для существует вероятностей, для только вероятностей, потому что первые битов заданы . Для снова существует вероятностей. Для существует только одна вероятность: . Мы будем продолжать, пока не достигнем последних двух точек. Для мы снова имеем почти вероятностей, и для только одна вероятность. Таким образом, общее число наборов точек . Сложность CPA-1 равна . Мы хотим, чтобы это число было как можно меньше, но при этом имелось максимум наборов точек длиной , которые удовлетворяли бы входным условиям. Поэтому необходимо, чтобы было настолько большим, насколько это возможно. Каждый набор с вероятностью равной удовлетворяет внутренние условия. Для реального шанса реализации этих условий необходимо . Если мы получим . Но это возможно только в том случае, если , т.е. при . Если , то необходимо взять максимальное значение для : , это даст CPA-1 сложность равную .


Все случаи приведены в таблице 3.

Лучшие CPA-1 атаки: R1, R2. Симуляция

CPA-1 атаки

В этом разделе мы опишем лучшие CPA-1 атаки, которые мы получили. Как и в прошлом случае, лучшие атаки у нас будут при . Исключение составляют раунды, в них мы получим более высокую сложность, чем в [3]. Как правило, лучшие CPA-1 атаки – это R2 атаки. Иногда R1 атаки обладают той же сложностью. Интересно отметить, что лучшие CPA-1 не получены из лучших KPA атак. Мы будем использовать расчеты CPA-1, произведенные в разделе 7. Мы опишем CPA-1 от до , лучшими атаками являются TWO атаки, рассмотренные в [3]. Как и в прошлый раз, мы дадим пример такой атаки для каждого раунда. Мы заметили, что при тех же условиях на входных и выходных переменных, мы можем найти несколько атак: горизонтальные и вертикальные условия на внутренних переменных могут по-разному отображаться в атаке, но мы должны соблюдать соотношение между числом уравнений и переменных на каждом этапе атаки. В конце данного раздела приведен пример. Наши лучшие R2 CPA-1 атаки приведены в следующей таблице:

Таблица 4. Лучшие из известных CPA-1 атаки на для любых
Значение Сложность

Замечание. Для , , и , существуют R1 атаки с одинаковой сложностью и одинаковым числом точек.

Обзор R2 CPA-1 атаки на Обзор R2 CPA-1 атаки на F k 3 k − 1 {\displaystyle F {k}^{3k-1}}

Мы создали симуляцию нашей лучшей CPA-1 атаки. Условия входа и выхода были следующие:

... ...
Раунд ... Раунд ...

Несколько различных дифференциальных способов соответствуют этим входным и выходным условиям. Например, рассмотрим все R2 варианты для и перестановок. См. таблицу 5 и таблицу 9, приложение А.

Таблица 5. Все варианты R2 атак на ,
Вариант 1:
0
1
2
3
4
5
6
7
8
Вариант 2:
0
1
2
3
4
5
6
7
8

Мы посчитали количество методов для :

3 4 5 6 7
метод? 2 8 27 89 296


Мы можем увидеть, что, чем больше , тем лучше работают атаки.

Экспериментальные результаты

Мы создали симуляцию этих CPA-1 атак. Для каждой модели, мы создаем случайную схему Фейстеля с 20 раундами и схему. Для обеих схем, мы вычисляем зашифрованных/открытых пар, изменяя только последние бит. После этого, мы выделяем все пары точек, удовлетворяющих входным и выходным условиям. Мы сортируем эти пары точек, чтобы подсчитать, сколько наборов точек совпадают с входными и выходными условиями. Если бы мы нашли пар точек, удовлетворяющих всем этим условиям с , мы рассчитываем, как будто мы нашли наборов длиной φ, потому что это число наборов, при котором мы можем выбирать эти точки, изменяя положение пары точек. После этого мы сравниваем количество найденное для перестановки. В большинстве случаев это позволяет нам видеть различия между ними. См. таблицу 6.

Сводные данные атак

В таблицах 7 и 8, мы приводим сложность атак, которые мы нашли. Для мы сформировали лучшие из возможных атак.

Таблица 6. Экспериментальные результаты для
успеха ложной тревоги итераций
2 3 6 29,09 0,35 100000
2 4 8 61,6 0,06 10000
2 5 10 98,37 0 10000
2 6 12 99,99 0 10000
2 7 14 100 0 1000
2 8 16 100 0 1000
2 9 18 100 0 500
2 10 20 100 0 100
4 3 12 21,15 1,12 10000
4 4 16 42,5 0 1000
4 5 20 93 0 100
4 6 24 100 0 100
6 3 18 8 1,2 500
8 3 24 2 0 100


Затем обобщим результаты для , и получим, что атаки, представленные здесь, являются наилучшими из возможных. Для у нас есть TWO атаки. Для у нас есть прямоугольная атаки. Как упоминалось ранее, в KPA всегда есть R2 и R3 атаки, которые дают лучшую сложность, иногда есть также R1 атаки ( раундов, например). В CPA-1, лучшая сложность определяется R2 атаками, а иногда и R1 атаками.

Таблица 7. Лучшие из известных TWO и прямоугольных атак на . Подробнее о параметрах из этой таблицы: (новая) обозначает, что мы обнаружили лучшую атаку, чем ранее известные.
KPA CPA-1
1 1
, TWO 2
, TWO 2
, TWO , TWO
, TWO , TWO
, R2, R3 , R2(новая)
, R1, R2, R3 , R2
, R2, R3 , R2


Таблица 8. Лучшие из известных TWO и прямоугольных атак на , при любых . Подробнее о параметрах из этой таблицы: (новая) обозначает, что мы обнаружили лучшую атаку, чем ранее известные.
KPA CPA-1
1 1
, TWO 2
, TWO 2
, , TWO 2
, TWO , TWO
, TWO , TWO
, R2, R3 , R2(новая)
, R1 R2, R3 , R2(новая)
, R2, R3 , R2(новая)
.

.

.

.

.

.

.

.

.

, , , R1 R2, R3 , R2(новая)
, , , R2, R3 , R2(новая)
.

.

.

.

.

.

.

.

.

, R2, R3 , R2(новая)
, R1 R2, R3 , R2(новая)
, R2, R3, (*) , R2

В этих таблицах "новая" означает, что сложность, которую мы получаем, лучше сложности рассмотренной в [3]. (*) Означает, что для раундов наши сложности хуже, чем сложности в [3]. Это происходит от того, что, как мы уже упоминали ранее, не все соотношения уравнений и внутренних переменных рассматриваются в [3].

Заключение

В этой статье произведен систематический анализ общих прямоугольных атак на несбалансированные конструкции Фейстеля расширяющими функциями. Хотя эти атаки были уже проанализированы в [2] и [3], эта статья достаточно сильно улучшена. Генерация всех возможных прямоугольных атак для была выполнена благодаря компьютерной программе, и были выбраны наиболее эффективные атаки. Так обобщение для любых становится возможным. Это дает атаки, для которых условия между уравнениями и внутренних переменных удовлетворены. Это не было обнаружено в [3]. Мы также предоставляем полное описание способа получения CPA-1 из KPA. Этот способ демонстрирует получение лучшего CPA-1, и мы улучшили CPA-1 сложность [3]. Кроме того, многие симуляции подтверждают наши теоретические результаты.

Есть еще некоторые нерешенные задачи. Было бы интересно, чтобы завершить программу в целях получения всех атак для любого . Это похоже на проблему объема памяти. Кроме того, в этой статье мы не изучали атаки с большей сложностью, чем . В этом случае, мы должны атаковать генераторы перестановок, а не только одну перестановку. В [3], были введена атаки, называемые «мульти-прямоугольными атаками», но до сих пор не было получено никаких существенных результатов с этими атаками. Это может открыть новый подход к изучению общих атак на несбалансированные конструкции Фейстеля расширяющими функциями. Как мы уже упоминали в разделе 3, когда у нас есть одинаковые условия на входных и выходных переменных, существует множество возможных CPA-1 атак (для , существует 286 атак на с одинаковыми условиями на входных и выходных переменных). Оценка любого будет усиливать атаку.

Контакты авторов материала

  1. Department of Mathematics, University of Cergy-Pontoise, CNRS UMR 8088 2 avenue Adolphe Chauvin, 95011 Cergy-Pontoise Cedex, France, E-mail: [1]
  2. Department of Mathematics, University of Cergy-Pontoise, CNRS UMR 8088 2 avenue Adolphe Chauvin, 95011 Cergy-Pontoise Cedex, France, E-mail: [2]
  3. PRISM, University of Versailles 45 avenue des Etats-Unis, 78035 Versailles Cedex, France E-mail: [3]
ctions]]

Литература

  1. L. Goubin, M. Ivasco, W. Jalby, O. Ly, V. Nachef, J. Patarin, J. Treger, and E. Volte. CRUNCH. Technical report, Submission to NIST, October 2008.
  2. 2,0 2,1 2,2 2,3 2,4 2,5 C. S. Jutla. Generalized Birthday Attacks on Unbalanced Feistel Networks. In Hugo Krawczyk, editor, Advances in Cryptology – CRYPTO ’98, volume 1462 of Lecture Notes in Computer Science, pages 186–199. Springer-Verlag, 1998.
  3. 3,00 3,01 3,02 3,03 3,04 3,05 3,06 3,07 3,08 3,09 3,10 3,11 3,12 3,13 3,14 3,15 3,16 3,17 3,18 3,19 3,20 3,21 3,22 J. Patarin, V. Nachef, and C. Berbain. Generic Attacks on Unbalanced Feistel Schemes with Expanding Functions. In Kaoru Kurosawa, editor, Advances in Cryptology – ASIACRYPT 2007, volume 4833 of Lecture Notes in Computer Science, pages 325–341. Springer-Verlag, 2007.
  4. M. Luby and C. Rackoff. How to Construct Pseudorandom Permutations from Pseudorandom Functions. SIAM J. Comput., 17(2):373–386, 1988.
  5. 5,0 5,1 M. Naor and O. Reingold. On the Construction of Pseudorandom Permutations: Luby-Rackoff Revisited. J. Cryptology, 12(1):29–66, 1999.
  6. J. Patarin. Security of Random Feistel Schemes with 5 or More Rounds. In Matthew K. Franklin, editor, Advances in Cryptology – CRYPTO 2004, volume 3152 of Lecture Notes in Computer Science, pages 106–122. Springer-Verlag, 2004.
  7. W. Aiello and R. Venkatesan. Foiling Birthday Attacks in Length-Doubling Transformations - Benes: A Non-Reversible Alternative to Feistel. In Ueli M. Maurer, editor, Advances in Cryptology – EUROCRYPT ’96, volume 1070 of Lecture Notes in Computer Science, pages 307–320. Springer-Verlag, 1996.
  8. J. Patarin. New Results on Pseudorandom Permutation Generators Based on the DES Scheme. In Joan Feigenbaum, editor, Advances in Cryptology – CRYPTO ’91, volume 576 of Lecture Notes in Computer Science, pages 301–312. Springer-Verlag, 1991.
  9. L. R. Knudsen. DEAL - A 128-bit Block Cipher. Technical Report 151, University of Bergen, Department of Informatics, Norway, february 1998.
  10. . L. R. Knudsen and V. Rijmen. On the Decorrelated Fast Cipher (DFC) and Its Theory. In Lars R. Knudsen, editor, Fast Software Encrytion – FSE ’99, volume 1636 of Lecture Notes in Computer Science, pages 81–94. Springer-Verlag, 1999.
  11. A. Yun, J. H. Park, and J. Lee. Lai-Massey Scheme and Quasi-Feistel Networks. Cryptology ePrint archive: 2007/347: Listing for 2007.
  12. J. Patarin, V. Nachef, and C. Berbain. Generic Attacks on Unbalanced Feistel Schemes with Contracting Functions. In Xuejia Lai and Kefei Chen, editors, Advances in Cryptology – ASIACRYPT 2006, volume 4284 of Lecture Notes in Computer Science, pages 396–411. Springer-Verlag, 2006.
  13. L. Goubin, M. Ivasco, W. Jalby, O. Ly, V. Nachef, J. Patarin, J. Treger, and E. Volte. CRUNCH. Technical report, Submission to NIST, October 2008.
  14. R. J. Anderson and E. Biham. Two Practical and Provably Secure Block Ciphers: BEARS and LION. In Dieter Gollman, editor, Fast Software Encryption, volume 1039 of Lecture Notes in Computer Science, pages 113–120. Springer-Verlag, 1996.

Приложение

Приложение А. Все варианты атак R2 на ,

Таблица 9. Все варианты атак R2 на ,