Линейные смещения, статистические атаки насыщения, алгоритм PRESENT и криптоанализ PUFFIN

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 20:55, 27 сентября 2015.
On Linear Hulls, Statistical Saturation Attacks,PRESENT and a Cryptanalysis of PUFFIN
Multi-query Computationally-Private Information Retrieval with Constant Communication Rate.PNG
Авторы Gregor Leander
Опубликован DTU Mathematics Technical University of Denmark G.Leander@mat.dtu.dk
Перевели коллектив проекта «Gir»
Год перевода 2011 г.
Скачать оригинал

__NUMBEREDHEADINGS__

Аннотация.. Мы обсуждаем сложность передовых линейных атак. В частности, мы утверждаем, что часто бывает проще оценить среднюю сложность вместо самого среднего значения. Более того, мы применяем эти методы к блочным шифрам PUFFIN и PRESENT. Для 128 битного шифра PUFFIN мы представляем атаку, которая нарушает шифр,по крайней мере, для четверти ключей со сложностью меньшей, чем . Для PRESENT мы покажем, как создать правильное построение. Критериев проектирования достаточно много для обеспечения устойчивости к линейным атакам, принимая во внимание понятия линейных оболочек. Наконец, мы покажем, что статистические атака насыщения и многомерные линейные атаки практически идентичны.

Введение

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

Одной из таких атак будет линейная атака Мацуи [1]. Несмотря на открытие более чем 15 лет назад, линейный криптоанализ все еще остается менее изученным, чем, например, дифференциальные атаки. В частности, для сложных линейных атак, таких как, атака с использованием линейных оболочек или многомерного криптоанализа, мы до сих пор не знаем, как правильно оценить их время работы. Рассмотрение линейных атак с использованием линейных оболочек Мерфи [2] приводит к весьма фундаментальной проблеме при оценке воздействия этих атак.

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

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

Наш вклад

В разделе 3 настоящей работы мы подробно обсудим проблемы, введенные Мерфи [2] для линейных оболочек. Тем не менее, мы не совсем согласны с выводом , что линейные оболочки не существуют. Напротив, мы объясним, почему линейных оболочки (правильно определенные) всегда существуют, и всегда должны быть приняты во внимание при анализе сложности атак. Для того, чтобы быть в состоянии сделать обоснованные утверждения о сложности атаки мы объясним, почему парадигма переходит от обсуждения средней сложности в целом к обсуждению промежуточных сложностей. Как мы покажем, это справедливо не только для атак с использованием линейных оболочек, но на самом деле и для линейных атак, основанных на одном линейном следе. Мы приводим методы, которыми можно, во многих случаях, вычислить приближенныесредние сложности.

В качестве примера, мы применяем наши методы для криптоанализа блочного шифра PUFFIN (cм. раздел 4). Мы представляем атаку для полного блочного шифра PUFFIN с 128-битным ключом, позволяющим восстановить 4 бита для последнего исполнения ключа, по крайней мере для четверти ключей со сложностью меньше .

В разделе 5 мы используем методы анализа устойчивости шифра PRESENT в линейном криптоанализе. Самое интересное мы показываем, что известный принцип построения шифра PRESENT не корректен в том смысле, что любой s бокс и любая бит перестановка, соответствующие критериям построения PRESENT приводят к потере безопасности шифра против таких линейных атак. Для того, чтобы сделать это, мы представляем связь между оптимальными бит перестановками и центральными орграфами, что уже интересно само по себе. Ключевыми орграфами будут классические комбинаторные объекты (см. например, [3]), а связь позволит нам ответить на естественные вопросы оптимальных перестановок. Самое главное, что эта связь позволяет нам классифицировать все оптимальные бит перестановки. Эта классификация позволяет нам получить более глубокое понимание блочного шифра PRESENT.

Наконец, в разделе 6 мы решаем задачу оценки отклонений для статистических атак насыщения. Использование теорему преобразования Фурье для булевых функций позволяет показать, что статистические атаки насыщения, в принципе, идентичны многомерным линейным атакам. В частности, эта связь позволяет нам оценить смещения, используемые в статистических атаках, с применением хорошо изученных инструментов и хорошо обоснованных теорий, что до сих пор является главным недостатком статистических атак насыщения. Кроме того, мы считаем, что эта связь позволяет применить статистические атаки насыщения к другим шифрам.

Предварительные сведения

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

Смещения, корреляции и преобразования Фурье

Обозначим через двоичное поле из двух элементов и через n-мерное векторное пространство для . Каноническое скалярное произведение для обозначается как , то есть

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

С учетом вероятности p линейного приближения для , т.е.

смещение линейного приближения для определяется как

что можно переписать в виде

Связь между преобразованием Фурье для F и смещением линейного приближения рассчитывается с использованием

что подразумевает

Кроме того, из-за масштабирования, часто бывает полезно сказать о корреляционных коэффициентах F. Они определяются как

что определяет потенциал в [4]. В [5] используется квадратичное евклидово расстояние,которое определяется как

и отличается от Cap(F) на коэффициент , то есть .

Существует важное, и хорошо известное отношение между емкостью (или евклидовым расстоянием) и преобразованием Фурье для F , которое мы будем использовать далее (см. например, [6]).

TemplateLemmaIcon.svg Лемма «Лемма 1.»


Линейные следы, корреляции и линейные оболочки

Рассмотрим отображение , являющееся сочетанием отображений, т.е. . Корреляции в этом случае могут быть вычислены с использованием линейных следов. Линейный след состоит из маски ввода a , маски вывода b и вектора с . Соотношение следов определяется следующим образом

Теперь, используя корреляционные матрицы [7] или преобразование Фурье для композитных отображений [8], можно доказать, что

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

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

Предположение, необходимое для понимания распределения смещений в линейной атаке, заключается в следующем.

Условие 1. Знаки в уравнении 2 независимо и равномерно распределены по отношению к ключу.

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

Другой важный результат, который мы будет использовать (см. теорему 1 в [6] и теорему 7.9.1 в [7]) состоит в следующем.

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

Статистические атаки насыщения

В этом разделе мы кратко опишем идею статистических атак насыщения. Детали приводятся в работе [5]. Учитывая функцию шифрования

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

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

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

Применяя лемму 1 к мы можем переписать значение с точки зрения коэффициентов Фурье для .


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

Эффект линейной оболочки

Линейные оболочки были изучены в [8] и с тех пор были использованы в ряде работ. Основная идея заключается в рассмотрении нескольких, иногда многих, линейных маршруты с неизменными входными и выходными масками для уменьшения сложности линейных атак с использованием алгоритма Мацуи. Однако, как указал Мерфи [2], существуют (как минимум) две проблемы, часто рассматриваемые в литературе. В этом разделе мы сначала вспоминаю две фундаментальные проблемы, и обсудим их влияние на сложность линейных атак. Хотя нашей отправной точкой является работа Мерфи, наши выводы вполне ортогональны. Более точно, мы считаем, что лучшее, чем предположение Мерфи о том, что не существует линейного эффекта оболочки, утверждает, что всегда есть линейный эффект оболочки, и мы всегда имеем дело с ним. Кроме того, мы предлагаем методы, которые позволяют нам добиться существенного успехов для времени работы линейных атак. В частности, мы покажем следующее.

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


Первая проблема Мерфи вытекает из неправильной формализации. Рассмотрим простейший случай двух линейных путей с одинаковыми входными и выходными масками, но с различными промежуточными масками. Предлагаемая лемма используется для оценки смещения (скажем, ) для каждого уравнения. Мы предполагаем, что и . Обозначим через α входную маску, через β выходную маску, а , будут двумя масками ключей, в итоге мы получим два уравнения

где первое уравнение справедливо со смещением , а второе со смещением . Теперь мы переходим к рассмотрению любых фиксированных (расширенных) ключей K. Мы рассмотрим два случая. Во-первых, мы имеем ключ . В этом случае мы получаем одно и то же уравнение дважды, подразумевая, что . С другой стороны, другой ключ дает , и в этом случае мы заключаем, что . Вероятнее всего существует, по крайней мере, один ключ для каждого случая, единственно возможным выбором для смещения будет , что противоречит нашему предположению. Что же произошло? Где появилась ошибка? Основным моментом здесь является то, что применение леммы неявно предполагает наличие независимого и равномерного распределения в каждом круге. Однако, зная первый маршрут, мы отмечаем, что входы распределены неравномерно, и, следовательно, это предположение неверно. Важно заметить разницу с подходом, использующим корреляционные матриц, то есть уравнение 2. Здесь нет никаких предположений относительно независимости или равномерности распределения. Таким образом, мы имеем дело с выражением

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

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

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

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

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

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

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

TemplateDifinitionIcon.svg Определение «Определение - Определение 1»
Медианой сложности будет такое , что для половины ключей сложность атаки меньше или равна . То есть можно было бы изучать сложности , определенные для вероятности данного ключа сложности ниже, чем , есть р

Заметим, что .

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

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

Кроме того, обозначим через корреляцию того, что вероятность данного ключа дать корреляцию больше или равную равна , с учетом маршрутов. Это приводит к уравнению

Обозначив корреляцию для оставшихся маршрутов , мы получаем

С вероятностью в 1/2 для суммы иметь тот же знак, что и .

Таким образом

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

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

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

Маршруты с одинаковыми абсолютными значениям и

Как уже было сделано ранее (см. [9]) для случая линейных маршрутов с одинаковыми абсолютными значениями распределение корреляции будет определяться как

Где это абсолютные смещения маршрутов, которые можно аппроксимировать нормальным распределением. Это приближение неявно использует предположение 1. Очевидно, что это предположение должно быть обосновано для каждого шифра путем экспериментов (мы делаем это далее для блочного шифра PUFFIN). Обозначая через X случайную величину, соответствующую смещению, мы будем аппроксимировать ее распределение

т. е. Х имеет нормальное распределение с нулевым средним и дисперсией . Функция плотности вероятности, таким образом, задается как

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

Используя соотношение для нормального распределения мы можем упростить G (t) до

где является функцией Гаусса. Медианой для Y, по определению, такое значение , что . Мы получаем

используя приближение мы получаем, что .

Для полноты картины, мы можем вычислить среднее для Y, как что соответствует предположению 1 (без использования нормального приближения).

Таким образом, использование нормального приближения в уравнении 7 позволяет заключить, что для четверти ключей атаки имеют сложность меньше малой константы . Аналогичный расчет показывает, что доля в 0,317 ключей приводит к атакам со сложностью порядка .

Линейные оболочки и PUFFIN шифр

Этот раздел применяет идеи, изложенные выше, к блочному шифру PUFFIN [10]. PUFFIN это 64-битный шифр с 32 циклами и 128 битным мастер ключом. Мы заинтересованы здаесь только в линейных слоях для s бокса. Линейными слоями будут следующие перестановки.

Рис. 1.

S бокс состоит из 16 параллельных исполнений одного 4-битного s бокса, как показано в таблице.

x 0 1 2 3 4 5 6 7 8 9 A B C D E F
S(x) D 7 3 2 9 A C 1 F 4 5 E 6 0 B 8


Главное отличие от PRESENT состоит в том, что для всех компонент можно сэкономить место при расшифровке цепи. Для более подробного анализа шифра PUFFIN можно просмортеть работу [10].

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

Линейные маршруты в шифре PUFFIN

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

Round/Level 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
4 2.00 - 1.00 - - - - - - - - - - - - - -
5 2.81 - 2.58 - - - - - - - - - - - - - -
6 3.32 - 4.00 2.00 1.00 - - - - - - - - - - - -
7 3.81 - 5.13 3.32 4.09 2.58 - - - - - - - - - - -
8 4.17 - 6.00 4.58 5.95 4.46 3.32 - - - - - - - - - -
. . . . . . . . . . . . . . . . .
28 7.70 - 13.41 12.69 17.78 18.04 21.51 22.05 24.47 25.18 26.89 27.63 28.84 29.50 30.34 30.87 31.41
29 7.80 - 13.61 12.90 18.19 18.36 21.91 22.48 24.98 25.72 27.52 28.30 29.58 30.30 31.22 31.81 32.43
30 7.89 - 13.80 13.09 18.47 18.66 20.30 22.89 25.48 26.25 28.12 28.94 30.30 31.07 32.06 32.71 33.41
31 7.99 - 13.99 13.29 18.76 18.95 22.67 23.28 25.95 26.75 28.70 29.55 30.99 31.80 32.86 33.57 34.34

Приближение для распределения смещений

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

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

где F является интегральной функцией распределения .

Для того, чтобы оправдать приближение, то есть неявное предположение о случайном поведении знаков, мы экспериментально вычисляем смещение для 1000 ключей для циклов от 7 до 10. Результаты представлены на рисунке 1.

Обратим внимание, что одна причина небольшой разницы состоит в том, что оценка небольших смещений не правильна, в связи с ограниченным количеством образцов. Кроме этой маленькой ошибки, распределение близко к среднему. Используя уравнение 8 можно вычислить средние значения. Оказывается, что базовые два логарифма для квадратичного смещения являются практически аффинными функциями. Хорошим приближением среднего квадратичного смещения для циклов r будет . В частности, применение теоремы 2 означает, что для четверти ключей сложность данных для нападения r циклов для PUFFIN шифра пропорциональна значению . Экспериментальные результаты для 7 по 12 атак (еще раз, используя 1000 случайно выбранных ключей в цикле) показывают, что использование дает полный выигрыш, то есть успешно восстанавливает четыре ключевых бита последнего цикла, в более чем 40% случаев. В частности, для r = 32, то есть для полного шифра PUFFIN, мы получаем сложность порядка .

Рис. 2. Теоретические оценки для экспериментальных смещений от 7 до 10 раундов. Экспериментальные данные основаны на 1000 случайно выбранных ключах для каждого цикла.


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

Линейные оболочки и шифр PRESENT

Шифром PRESENT является 64-разрядный блочный шифр, разработанный А. Богдановым и соавт. [11] и предназначенный для недорогих устройств, таких как RFID-теги. Есть две версии, 80 битная, называемая PRESENT-80 и 128 битная версия, PRESENT-128. PRESENT это подстановочная сеть с 31 циклом и одним финальным ключевым исполнением в конце.

В замещенной слое (так называемом s бокс слое для PRESENT) для 4-бит S бокс применяется 16 раз параллельно. Действие s бокса в шестнадцатеричной системе дается в следующей таблице.

x 0 1 2 3 4 5 6 7 8 9 A B C D E F
S[x] C 5 6 B 9 0 A D 3 E F 8 4 7 1 2

Слой перестановок (так называемый p слой для PRESENT) задается как простая бит перестановка. Бит i текущего состояния перемещается в позицию Р (i), где

S бокс для PRESENT был выбран для выполнения нескольких критериев(см. [11]), чтобы обеспечить возможность дифференциального и линейного криптоанализа. Мы называем такой s бокс оптимальным.

По сравнению с общим линейным слоем случай слоя перестановок в PRESENT обеспечивает относительно низкую диффузию. Однако, как отмечалось в [11], для бит перестановки p слой является оптимальным в том смысле, что полная зависимость достигается уже после минимального количества циклов. После трех циклов каждый из 64 входных битов влияет на все 64 выходных бита. Для удобства мы называем такие перестановки оптимальнымиl. Более подробную информацию по шифру PRESENT можно найти в [12].

Линейные атаки на шифр PRESENT

В ряде работ обсуждаются линейные атаки на шифр PRESENT. В работе [9] линейные оболочки использовались для атаки на 25 циклов. Более того, в [6] описываются многомерные линейные атаки на вплоть до 26 циклов шифра PRESENT. Основная причина, по которой линейный криптоанализ применим для 26 циклов шифра PRESENT это относительно большое количество линейных маршрутов с одним активным s боксом для каждого цикла. Так как увеличение числа линейных маршрутов не обсуждалось в [12] то остается важный вопрос, насколько правильно построение PRESENT для линейных оболочек. Для обозначим через N(а,b) число линейных маршрутов, начиная с входного бита a, и заканчивая выходным битом b и лишь с одним активным s боксом на цикл.

Выбор S бокса и перестановки в PRESENT

В данном случае мы заинтересованы в понимании влияния выбора s бокса и бит перестановок на максимальное количество маршрутов N (а,b). Как объяснялось ранее, при использовании результатов классификации по оптимальному s боксу и основных орграфов можно заключить, что

  • Учитывая бит перестановку для PRESENT, s бокс принадлежит 8% худших из оптимальных s боксов.
  • Учитывая s бокс для PRESENT, бит перестановка будет наихудшей среди примерно оптимальных испытанных перестановок.

Следует отметить, что использование бит перестановок для PRESENT это обычная практика. Тем не менее, s боксы в PRESENT выбираются среди всех возможных оптимальных вариантов с наименьшим аппаратными затратами. Мы оставляем в качестве темы для дальнейших исследований вопрос о наличии корреляции между размером аппаратных цепей и числом маршрутов.

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

Самое главное, что результаты, изложенные ниже, подразумевает, что принцип построения PRESENT является неккоректным в следующем смысле.

Ни для одной комбинации оптимальный s бокс и оптимальная бит перестановка линейной атака не представляются возможными для 31 цикла.

Влияние S бокса. В этом параграфе мы фиксируем бит перестановки, использованные в PRESENT, и вычисляем максимальное количество маршрутов для различных выбранных S боксов. При добавления констант до и после s боксов, не меняющих любой из этих критериев, а тем более не меняющих линейные маршруты, существует ровно 8064 таких s боксов (см., например,[12]). Для каждого возможного s бокса, соответствующего этим критериям, мы вычислили максимальное число однобитных маршрутов для всех входных / выходных бит комбинаций 31 цикла. Оказывается, что есть только 31 возможное значение для этого максимума, от 0 и примерно до . В таблице 1 приводится число s боксов (из 8064 возможных) по каждому из 30 возможных значений для максима маршрута. S бокс для PRESENT имеет максиму порядка и таким образом, находится среди 8 процентов наихудших оптимальных s боксов.

Таблица 1. Максимальное количество маршрутов в зависимости от числа s боксов (из 8064). Для случаев, когда использовалась бит перестановка в PRESENT.

Maximal Number of Trails 0 3.00 6.965 7.754 9.509 9.965 10.75 12.26
Number of sboxes 96 1056 192 48 48 192 768 48 48
Maximal Number of Trails 15.00 16.47 17.42 19.42 21.47 21.71 22.86 24.29 29.25
Number of sboxes 144 48 48 816 96 48 48 96 864
Maximal Number of Trails 25.30 25.54 25.75 26.03 26.04 26.08 26.33 26.34 26.37
Number of sboxes 96 96 96 96 96 96 96 96 96
Maximal Number of Trails 26.60 27.00 38.17 39.47
Number of sboxes 96 1728 384 192

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

Первая проблема состоит в том, что на самом не так легко найти такую перестановку 64 бит, чтобы в PRESENT SP сети выход приводид к полной зависимости после трех циклов. Оптимальное перестановки редко встречаются. Однако, есть интересная связь с хорошо изученными объектами в теории графов, а именно с основными орграфами, что позволяет преодолеть эту проблему.

TemplateDifinitionIcon.svg Определение «Определение - Определение 2»
Пусть n будет целым и D будет ориентированным графом с n вершинами. D называется центральным, если существует уникальный ориентированный путь длины два между любыми двумя его вершинами.

Как известно (см. [3]) центральные графы существуют только при и когда каждая вершина имеет степени 4 в обе стороны.

Любая оптимальная бит перестановка приводит к центральному орграфу следующим образом. К 16 s боксам и 16 вершинам мы добавляем дуги направленые от вершины i к вершине j, только если существует выходной бит s бокса i, который получается отображением на бит s бокса j. Ясно, что каждая из 16 вершин имеет степень 4. Для оптимальной перестановки учитывается также тот факт, что каждая вершина (то есть каждый s бокс) может быть достигнута из любой другой вершины (то есть любого другого s бокса) за два этапа. Подсчеты показывают, что такой путь должен быть уникальным и поэтому полученный граф действительно будет центральным орграфом.

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

TemplateTheoremIcon.svg Теорема Теорема 4
До перестановки входных и выходных битов каждого s бокса существует взаимно однозначное соответствие между оптимальными перестановками 64 битов и центральным орграфом порядка 16.
Доказательство
Интересно отметить, что бит перестановка для PRESENT фактически соответствует Известному "стандартному примеру" с точки зрения центральных орграфов. Множество вершин для стандартного примера состоит из всех пар (х, у), при и , когда.


Используя эту связь можно ответить на несколько интересных вопросов. Например, есть необходимость избежать оптимальной перестановки, в которой бит из одного s бокса отображается на тот же s бокс в следующем цикле. Тем не менее, хорошо известно (см. например, [3]), что каждый центральный орграф из вершин имеет ровно k циклов. Этот приводит к тому, что оптимальная перестановка 64 бит будет отображать точно 4 входных бита (из 4 различных s боксов) обратно в исходный s бокс.

Для наших целей наиболее интересен тот факт о центральном орграфе, что классификация всех центральных орграфов порядка 16 известна (см. [13]) и фактическое число (неизоморфных) центральных орграфов порядка 16 является разумно малым. С точностью до изоморфизма существует 3492 центральных орграфа порядка 16. Таким образом, эта связь позволяет сравнить большое разнообразие вариантов для оптимальных бит перестановок.

Мы фиксируем s бокс для шифра PRESENT и вычисляем количество маршрутов для всех 3492 возможных центральных орграфов. Здесь мы случайно сопоставили 4 входящих вершины и 4 исходящих вершины с входными и выходными битами s бокса в 1000 разных видах для каждого из 3492 центральных орграфов. Результат показан в таблице 2.

Опять таки, перестановка в PRESENT дает максимальное количество маршрутов порядка и, следовательно,в худшем случае выриантов.

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

Таблица 2. Максимальное количество маршрутов в зависимости от числа оптимальных перестановок (из 3492•1000) и для заданного числа маршрутов. Во всех случаях используется PRESENT s бокс.

#Trails 1 2 3 4 5 6 7 8 10
#permu. 2 5 7 8 16 21 46 51 86 144
#Trails 11 12 13 14 15 16 17 18 19 20
#permu. 234 351 559 990 1780 3260 5951 11187 21033 39284
#Trails 21 22 23 24 25 26 27 28 30
#permu. 71712 125520 205411 313402 431188 524990 553858 494911 359864 205508
#Trails 31 32 33 34 35 36 37 38
#permu. 87875 26257 5344 941 184 18 1 1

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

Рис. 3.

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

Понимание статистических атак насыщения

В этом разделе мы покажем, как потенциал статистических атак насыщения может быть объяснен с помощью инструментов линейного криптоанализа. Основным моментом будет тождество между преобразованием Фурье для булевой функции и смещением его ограничений (ср. с теоремой V.1 в [14], см. также предложение 9 в [15])

Предложение 2 (теорема V.1 в [14]). Пусть будет булевой функцией. Кроме того, пусть Е и Е' будут такими подпространствами для , что и чья прямая сумма равна . Для каждого пусть будет ограничением для на класс ( можно отождествить с функцией из , где это размерность для . Тогда

Здесь это ортогональное пространство для Здесь . Напомним, что мы принимаем функцию шифрования и ее ограничения,фиксируя последние входные s биты и рассматривая лишь первые выходные биты, то есть функцию , определенную уравнением 5. Для статистических атак насыщения мы заинтересованы в емкости, заданной формулой 6. Используя данного предложения , мы теперь представим основной результат этого параграфа.

TemplateTheoremIcon.svg Теорема Теорема 1
Теорема 5. С учетом указанных выше обозначений, средняя емкость статистических атак насыщения, где среднее берется по всем возможным фиксациям, задается как

Доказательство
По определению

Применяя тождество (9) для всех компонент функции (и ее ограничений ),где мы выбираем и , мы приходим к

С помощью этого мы выводим из (10).

что и требовалось.


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

С этой точки зрения, статистические атаки насыщения очень тесно связаны С многомерными линейными атаками. Статистические атаки насыщения для PRESENT, приведенные в [5] и многомерный линейный криптоанализ для PRESENT, приведенный в [6], в принципе это таже атака.

Статистические атаки насыщения для PRESENT

Описание PRESENT приведено в разделе 5, а более подробная информация в работе [12].

В этом разделе мы более внимательно рассмотрим статистические маршруты насыщения, используемые в [5] и объясним потенциал с использованием связи с линейными атаками. Картина маршрута в [5] приводится ниже.

Рис. 4.

В данном маршруте биты (считая справа налево, начиная с 0)

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

Определим , где это канонический базисный вектор, только с единицами в i позициях (считая от нуля), теорема 5 утверждает, что

Чтобы вычислить эту способность, мы должны вычислить коэффициенты корреляции для .

Как и в разделе 5 мы ограничимся единичного веса. Это было сделано также и в [10,6] для больших абсолбтных значений. Опять же, эти предположения подтверждаются экспериментальными данными, см. ниже. Для единичного веса мы напомнили в разделе 5, что существует много возможных линейных маршрутов, начиная со входной маски a и заканчивая выходной маской , где все промежуточные маски имеют единичный вес. Напомним, что мы обозначим число этих линейных маршрутов через . Кроме того, легко вычислить точное количество таких маршрутов для любой пары .

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

И

Мы сравнили экспериментальные расчеты усредненные для более чем 100 различных ключей и 10 различных значений y для каждого ключа, с результатами приближения (11). За исключением первых двух циклов экспериментальные данные довольно точно соответствуют приближению.

Round 2 3 4 5 6 7 8 9
5.00 6.00 7.32 8.64 9.97 11.34 12.72 14.10
approx. -11.00 -14.00 -16.68 -19.36 -22.03 -24.66 -27.28 -29.90
experimental -10.38 -13.82 -16.27 -18.90 -21.60 -24.13 -26.78 -29.26

По значениям для видно ,что данный маршрут не представляется оптимальным. Действительно, использование маршрута с фиксация входных битов S = {21, 22, 25, 26, 37, 38, 41, 42}, но на этот раз с ограниченым выходом S’ = {21, 23, 29, 31, 53, 55, 61, 63} дает лучшие результаты, теоретически. Определяя , сумма будет больше в сравнении с исходным маршрутом (например, емкость для 9 циклов это вместо ). Опять же, мы проверили это поведение экспериментально и экспериментальные данные подтверждают приближения.

Заключение и дальнейшая работа

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

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

Благодарности. Автор благодарен Шону Мерфи за очень ценные комментарии.

Литература

  1. 1,0 1,1 Matsui, M.: Linear cryptanalysis method for DES cipher. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 386–397. Springer, Heidelberg (1994)
  2. 2,0 2,1 2,2 Murphy, S.: The Effectiveness of the Linear Hull Effect. Technical Report, RHULMA-2009-19 (2009)
  3. 3,0 3,1 3,2 Knuth, D.: Notes on central groupoids. J. Combin. Theory 8, 376–390 (1970)
  4. Hermelin, M., Cho, J.Y., Nyberg, K.: Multidimensional extension of matsui’s algorithm2. In: Dunkelman, O. (ed.) FSE 2009. LNCS, vol. 5665, pp. 209–227.Springer, Heidelberg (2009)
  5. 5,0 5,1 Collard, B., Standaert, F.X.: A statistical saturation attack against the block cipher present. In: Fischlin, M. (ed.) CT-RSA 2009. LNCS, vol. 5473, pp. 195–210. Springer, Heidelberg (2009) (1994)
  6. 6,0 6,1 Cho, J.Y.: Linear cryptanalysis of reduced-round present. In: Pieprzyk, J. (ed.) CT-RSA 2010. LNCS, vol. 5985, pp. 302–317. Springer, Heidelberg (2010) (2009)
  7. Daemen, J., Rijmen, V.: The Design of Rijndael: AES - The Advanced Encryption Standard. Springer, Heidelberg (2002) (2009)
  8. Nyberg, K.: Linear approximation of block ciphers. In: Santis, A.D. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 439–444. Springer, Heidelberg (1995)
  9. 9,0 9,1 Ohkuma, K.: Weak keys of reduced-round present for linear cryptanalysis. In: Jacobson Jr., M.J., Rijmen, V., Safavi-Naini, R. (eds.) SAC 2009. LNCS, vol. 5867, pp. 249–265. Springer, Heidelberg (2009)
  10. 10,0 10,1 Cheng, H., Heys, H.M., Wang, C.: Puffin: A novel compact block cipher targeted to embedded digital systems. In: Fanucci, L. (ed.) DSD, pp. 383–390. IEEE, Los Alamitos (2008)
  11. 11,0 11,1 11,2 Bogdanov, A., Knudsen, L.R., Leander, G., Paar, C., Poschmann, A., Robshaw, M.J.B., Seurin, Y., Vikkelsoe, C.: Present: An ultra-lightweight block cipher. In: Paillier, P., Verbauwhede, I. (eds.) CHES 2007. LNCS, vol. 4727, pp. 450–466. Springer, Heidelberg (2007)
  12. Leander, G., Poschmann, A.: On the classification of 4 bit s-boxes. In: Carlet, C., Sunar, B. (eds.) WAIFI 2007. LNCS, vol. 4547, pp. 159–176. Springer, Heidelberg (2007)
  13. K¨undgen, A., Leander, G., Thomassen, C.: Switchings, extensions, and reductions in central digraphs (2010) (preprint)
  14. 14,0 14,1 Canteaut, A., Carlet, C., Charpin, P., Fontaine, C.: On cryptographic properties of the cosets of r(1, m). IEEE Transactions on Information Theory 47(4), 1494–1513 (2001)
  15. Carlet, C.: Boolean Functions for Cryptography and Error Correcting Codes (to appear)