Криптоанализ PRINTcipher: инвариантная подпространственная атака

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 13:26, 24 декабря 2015.
A Cryptanalysis of PRINTcipher: The Invariant Subspace Attack
Снимок.JPG
Авторы G.Leander,M.A.Abdelraheem,H.Alkhzaimi,E.Zenner
Перевели Kirill Kalinin
Год перевода 2015 г.


Аннотация

На CHES 2010 был представлен новый метод шифрования PRINTcipher. Данный метод представлялся как легковесный метод шифрования для реализации на печатных платах.

Лучший способ атаки на данные – это дифференциальная атака [1], которая приводит к успеху меньше чем за половину раундов. В данной статье мы представим новый способ атаки "инвариантная подпространственная атака" который ломает полный шифр по значимой части его ключа. Этот способ может рассматриваться как статистическая атака для слабого ключа. Для слабых ключей выбор способа атаки, направленной на распознавание открытого текста, может быть сделан за небольшое количество времени. Кроме того, для взлома PRINTcipher новая атака также даёт нам возможность по другому взглянуть на другие, широко известные атаки. Мы получили сокращенные дифференциальные характеристики с независимой от раунда, но очень зависимую от ключа вероятность. Кроме того, мы также показали существование слабых ключей, с сильно смещенной линейной аппроксимацией для любого количества раундов. Таким образом, PRINTcipher сильно отличается от того, чем он обычно представляется.

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

Введение

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

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

Использование таких методов как правило приводит к появлению нестандартных, недостаточно исследованных методов шифрования, что в свою очередь приводит к появлению атак, направленных против новых методов шифрования. Следует отметить, что конструирование атак против простых шифров часто позволяет лучше понять блочное шифрование в целом. Важно отметить, что атака для взлома простых шифров может быть не эффективна против обычного блочного шифра не только благодаря его структуре, но также по случайности: даже если атака не была известна во время разработки шифра, она может оказаться не опасной для него благодаря его высокой стойкости. Далее мы представим новый способ атаки, имеющий название «инвариантная подпространственная атака», предложенный на CHES 2010. При помощи этой атаки можно взломать PRINTcipher. Наилучшим известным на данный момент анализом PRINTcipher является дифференциальная атака, представленная на FSE 2011, которая может быть применена для менее чем половины раундов PRINTcipher, используя книгу полных кодов. Помимо того, что инвариантная подпространственная атака предоставляет возможность взлома PRINTcipher и обеспечивает нас новым инструментом для атаки блочных шифров, она также имеет отношение к другой широко известной технике атак. Этот факт улучшает наше понимание анализа блочных шифров в общем.

Наш вклад

В этой статье, в разделе 2.2, мы детально рассмотрим новую атаку на PRINTcipher. Атака основана на наблюдении, что для PRINTcipher существуют смежные классы из подпространства Fn2 , которые функция округления отображает на смежные классы того же подпространства. Точный смежный класс определяется только по ключу раунда. Итак, если ключ раунда такой же как смежный класс, отображенный на себя, тот факт, что все ключи раунда идентичны в PRINTcipher означает то, что для конкретных заданных слабых ключей некоторые смежные подпространства инвариантны при шифровании. Константы раунда, в основном, вводятся для того, чтобы избежать скользящих атак. Принципы атаки описываются в разделе 2.1. Используя новую технику атаки, которую мы назвали (по очевидным причинам) инвариантная подпространственная атака, мы продемонстрируем существование 252 слабых ключей для PRINTcipher-48 и 2102 слабых ключей для PRINTcipher-96. Если ключ слабый, результатом нашей атаки будет являться распознаватель, полученный[3]. с использованием менее чем 5 простых текстов или шифротекстов. То есть, даже в случае RFID- тегов, когда количество данных доступных для целесообразной атаки строго ограничено, наша атака применима. В случае известного сценария открытого или шифрованного текста сложность данных возрастает на коэффициент 216 PRINTcipher-48 и 232 для PRINTcipher-96. Кроме низкой сложности данных распознавателя, атака имеет интересное отношение к более широко известным атакам, которое мы хотели бы осветить. Во-первых, инвариантная подпространственная атака подразумевает использование сокращенной дифференциальной атаки, при которой вероятность сокращенной дифференциальной характеристики сильно зависит от ключа. Для слабых ключей вероятность 2-16 зависит от количества раундов, в то время как при не слабом ключе вероятность равна нулю для любого количества раундов большем или равном двум. Во-вторых инвариантная подпространственная атака может быть интерпретирована как статистическая атака. Слабый ключ вместе со специально выбранными битами статистической атаки, приводит к максимальному смещению, не зависимо от количества раундов. Обратите внимание на близкое отношение статистической атаки с многомерной линейной атакой. Мы покажем, что инвариантная подпространсвенная атака подразумевает существование сильно ангажированных линейной аппроксимаций слабых ключей, зависимых от количества раундов (более подробно описывается в разделе 4). Из этого следует, в частности, то, что PRINTcipher является примером реального шифра, для которого атаки ведут себя не так, как от них ожидается. Вероятность усеченных дифференциальных характеристик, смещение для статистической атаки и смещение линейной оболочки являются сильно зависимыми от ключа. Для слабых ключей увеличение количества раундов для полного количества раундов не увеличивает стойкость шифра к этим атакам.

Похожие работы

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

Инвариантная подпространественная атака

Общая идея

Рассмотрим n-битный блочный шифр с функцией округления Ek, состоящий из дополнения ключа и SP-слоя E: Fn2 Fn2, где Ek(x) = E(x+k). Ключ раунда k = u+c+d, u ∈ U, из чего следует:

Ek(U+d) = E((U+d) + (u+c+d)) = E(U+c) = U+d

то есть функция ключа раунда отображает аффинное подпространство U+d на себя. Если все ключи раундов k ∈ U + (c+d) (в частности, если используется постоянное количество раундов), то это свойство итеративно для произвольного числа раундов. Это также очень эффективный распознаватель для некоторых ключей. U должно быть максимально большим, для увеличения количества таких ключей. Мы назвали эту технику атаки Инвариантная подпространственная атака. В следующем разделе мы покажем пример того, как применять её для простого блочного шифра PRINTcipher.

Атака на PRINTcipher

Описание PRINTcipher

Pc – это блочный шифр предложенный Knusden на CHES 2010. Это класс двух SP-сетей с размером блока n = 48 бит, размером слова l = 80 бит и имеющий 48 раундов. Один раунд PRINTcipher-48 представлен на Рис.1.

Рис.1 Один раунд PRINTcipher-48.

PRINTcipher используется один и тот же ключ для всех раундов Он разделен на две части: первые n битов используются для результата исключающего или ключа, требуемых l-n битов отвечающих за перестановки p. Чтобы определить отличия между раундами, счетчик раундов RCi сгенерированный LSFR (подробно в[4]]). Другие части функции раунда описываются далее. Линейный уровень состоит из перестановки битов, в которой бит i текущего состояния перемещается на позицию P(i), где:

Далее, биты состояния распределяются в 16 блоков (по три бита в каждом), которые переставляются индивидуально на уровне перестановок. Из шести возможных перестановок по три бита только четыре являются правильными для Pc. А именно, три входных бита с2 || с1 || с0 переставляются для получения следующих выходных битов, в соответствии с двумя ключами бита a1 || a0.

В конце концов, на нелинейной уровне, каждый трехбитный блок обрабатывается таким же s-боксом, который представлен в следующей таблице:

Атака на PRINTcipher

Одним из интересных свойств s-бокса в PC является то, что один отличный бит на входе, приведет к тому, что на выходе получится тот же отличительный бит с вероятностью 2/8. То есть существует точно одна пара для каждого входного отличительного бита получаемая в бите выхода (на той же самой позиции). В следующем рисунке иллюстрирующем s-бокс, звездочкой отмечены произвольные значения:

Рис.2.jpg

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

Рис.2 Подмножество s-боксов PRINTcipher-48 отображаемых на себя.

Теперь рассмотрим xor-key sk1 в форме

Xor key = 01* *11 *** *** 01 *11 *** *** 01* *11 *** *** 01 *11 *** ***,

и перестановки ключа со следующими ограничениями:

Perm. key = 0* 11 ** ** 10 01 ** ** 11 *0 ** ** *0 11 ** **,

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

Рис.5.jpg

Это свойство выполняется с вероятностью равной единице, если оба ключа заданы в форме, указанной выше. Доля таких ключей равна (1/2)16 для XOR key и (1/2)13 для перестановки ключа. Это означает, что данное свойство встречается в (1/2)29 всех ключей. Другими словами, существует 251 слабых ключей такой формы. Таким образом, проверка на то, имеет ли ключ такую форму, может быть осуществлена достаточно эффективно посредством шифрования нескольких текстов в форме, представленной выше и проверки на то, остается ли шифротекст в той же форме. Вероятность ложных срабатываний приблизительно равна 2-16. Пробное шифрование небольшого количества простых текстов однозначно выявят слабые ключи. Если такой ключ найден, мы немедленно получаем распознаватель PRINTcipher.

Описание инвариантного подпространства

Позвольте нам коротко перефразировать атаку в терминах инвариантного подпространства. Для этого, мы зафиксируем ключ в представленной выше форме. Запомните, что внутреннее состояние начального и конечного раунда было:

Start = 00* *10 *** *** 00* *10 *** *** 00* *10 *** *** 00* *10 *** ***

Это означает, что соответствующее подпространство U ⊂ F248 определяется как:

U = {00* *00 *** *** 00* *00 *** *** 00* *00 *** *** 00* *00 *** ***},

и это аффинное подпространство определено как фиксированный вектор d в форме

d = 00* *10 *** *** 00* *10 *** *** 00* *10 *** *** 00* *10 *** ***

Далее, для любого фиксированного вектора c в форме:

c = 01* *01 *** *** 01* *01 *** *** 01* *01 *** *** 01* *01 *** ***,

и любого xor-key k ∈ (U + c + d), функция раунда в самом деле отображает U + d на себя.

Другие профили атаки

Далее, мы опишем другие наборы слабых ключей для PRINTcipher-48 и схожего с ним PRINTcipher-96.

Другие слабые ключи для PRINTcipher-48

Как выясняется, существует несколько дополнительных инвариантных подпространств, которые также могут быть использованы для PRINTcipher-48. Все они имеют следующую форму:

00* XXX *** 1*1 00* *10 *** *** 00* XXX *** 1*1 00* *10 *** ***,

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

Рис.6.jpg

Такое поведение наилучшим образом понимается путем выполнения шагов задом наперед. То есть начиная с конца и находя биты ключа, которые обеспечивают, что все зафиксированные биты в строке (1) совпадают с их аналогами в строке (6). Начнем с вывода s-бокса, то есть строки (6). Пусть позиции отмеченные как ‘X’ будут являться произвольными и равняться 1 или 0. Затем через s-боксы определяем биты в строке (5). Затем получаем ограничения ключа в форме:

Perm. Key = 0* ** ** (00 or 11) 10 01 ** ** 11 ** ** 10 0* 11 ** **

для достижения строки (4), важно, что 2-13 всех перестановок ключей имеют это свойство. Затем мы применяем счетчик раундов и линейный уровень, чтобы достичь строки (2). Обратите внимание, что строка (2) содержит 22 фиксированных бита, которые должны соответствовать битам в строке (1). Эти 22 бита являются ключевыми битами, подвергнутыми операции XOR. Это означает, что 2-22 всех ключей, подвергаемых операции XOR подходят для атаки. Таким образом, для каждого из 26 возможных присваиваний битам отмеченным как ‘X’ в строке (1) или (6), доля слабых точно равна 2-35. Это значит, что мы нашли дополнительно 2-29 слабых ключей, которые могут быть атакованы посредством техники, описанной выше.

Анализ PRINTcipher-96

Как известно, тип атаки, описанный ранее, может быть применен к PRINTcipher-96. Так же существует два типа слабых ключей. Первый тип имеет 32 активных бита и составляет 2-59 от общего количества ключей. Второй тип имеет 44 активных бита и дополнительно содержит 12 свободно выбираемых входных битов. Каждый из итоговых 212 вариантов входа составляют 2-71 часть всех ключей. Это означает, что эта группа содержит 2-59 часть слабых ключей.

Защита от атаки

Атака против PRINTcipher, описанная ранее является особым случаем общей атаки, описанной в начале главы, так как подпространство описано как простое фиксирование некоторых битов. В теории, описание подпространства при помощи системы линейный уравнений возможно расширит возможности атаки. Все возможности данной обобщенной атаки еще предстоит определить. Что касается специального метода, используемого против PRINTcipher, от него достаточно просто защититься. Следует отметить, что перечисление профилей атаки, путем фиксирования битов, описанное здесь конечно, и все профили атак фиксируют два бита 39-41 (PRINTcipher-48) или 87-89 (PRINTcipher-96). Таким образом, достаточно расположить счетчик раундов через последние три s-бокса, то есть присвоить два бита счетчика каждому s-боксу. Такие меры разрушат профили атаки без вычислительных затрат [5]].. Мы также проанализировали блочный шифр NOEKEON, который был предложен Daemen в 2000 году [9]. NOEKEON – это 16-раундный блочный шифр с постоянным количеством раундов, что делает его потенциальной целью для атаки. Однако, как выяснилось, уровень линейного смешивания данного шифра значительно более стойкий к описанному ранее типу атаки. Стойкая функция раунда (необходимая для шифра со строго 16 раундами) является преимуществом данного шифра. Как выяснилось, даже если в NOEKEON не использовать счетчик раундов, простая атака, описанная ранее (в которой подпространство определено фиксированными битами) не применима. Имеет ли обычная атака больше шансов на успех еще предстоит выяснить.

Сокращенные дифференциальные атаки

Как упоминал Murphy в[6], сложность линейной атаки часто определяется в литературе неверно. Одна из причин состоит в том, что часто бывает проще вычислить отклонение e2, когда при усреднении среди всех ключей. Как бы то ни было, часто утверждается, что средняя сложность атаки равна для малых γ что в общем случае неверно. На практике средняя сложность формально бесконечна если существует единственный ключ без смещения, в то время как конечна, если существует ключ со смещением. Докажем, что тоже самое верно для (сокращенной) дифференциальной атаки. Сокращенная дифференциальная характеристика на n-битном блоке, в общем случае, может быть описана множеством входных и выходных неравенств. Пусть Ui ⊂ Fn2 для 0≤i≤r и Ui Ui+1 множество дифференциальных характеристик с вероятностью pi Примем независимую среднюю вероятность ключей, вычисленную по всем ключам, сокращенной дифференциальной характеристики для r раундов за p.

U0  U1 ... Ur, где
p = pi

Согласно гипотезе стохастической эквивалентности [7], для большинства ключей справедливо pk ≈ p. Здесь pk обозначает вероятность сокращенной дифференциальной характеристики для заданного ключа k. Данное утверждение можно быть абсолютно неверно. В самом деле PRINTcipher является примером прямо противоположным. Далее мы покажем, что для PRINTcipher атака, описанная в разделе 2 подразумевает существование сокращенной дифференциальной характеристики, такой что pk ∈ {2-16, 0}, для любого количества раундов больше двух. Поскольку часть слабых ключей равна 2-29 от их общего количества, средняя вероятность по всем ключам

pav= 2-16*2-29=2-45

Напомним, что это справедливо для любого количества раундов r ≥2. После представления инвариантной подпространственной атаки существование такой сокращенной дифференциальной характеристики не должно быть удивительным. В свою очередь, это означает, что пары характеризующие два раунда, также характеризуют любое количество раундов. Как бы то ни было, это опровергает наивное предположение о том, что умножение вероятностей отдельных раундов дает среднюю сложность атаки, которая стремится к нулю при увеличении количества раундов. Это не только предположение о том, что все ключи в большей или меньшей степени неправильны. Также, предположение о том, что ключи раунда независимо приводят к очень неправильному заключению. Завершая эту часть, отметим, что средняя сложность не раскрывает поведения PRINTcipher. Даже наоборот, PRINTcipher ведет себя совершенно не так, как от него ожидается.

Представление Атаки в терминах сокращенных дифференциалов

В данном разделе, мы докажем приведенное ранее утверждение. Для того, чтобы упростить описание, рассмотрим версию PRINTcipher-48, в которой перестановка ключа имеет вид:

00 11 00 00 10 01 00 00 11 00 00 00 00 11 00 00

Один раунд PRINTcipher с данным ключом проиллюстрирован на Рис.3. Перестановки других слабых ключей ведут себя похоже.

Рис. 3 Один раунд PRINTcipher с зафиксированной перестановкой ключа. На линейной уровне показаны только те биты, которые влияют на дифференциальную характеристику.

Теперь рассмотрим r-раундную дифференциальную характеристику в форме

 U′ U...U U,

где задана как[8] = 000 100 011 101 000 100 001 100 000 000 001 110 001 000 101 110 и U′ содержит все вектора вида:

U′ = {001 100 **1 1** 001 100 **1 1** 001 100 **1 1** 001 100 **1 1**}.

Наконец, так же как в разделе 2, U определено как:

U = {00* *00 *** *** 00* *00 *** *** 00* *00 *** *** 00* *00 *** ***}.

Теорема 1. Для любого фиксированного ключа k, обозначим вероятность сокращенной дифференциальной характеристики, заданной равенством, через p: , где ключ k является слабым если и только если он имеет следующую форму:

k = 01* *11 *** *** 01* *11 *** *** 01* *11 *** *** 01* *11 *** ***.

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

E = F2n   F2n

исключающую начальное дополнение ключа и два подмножества:

A,B ⊆ F2n 

мы обозначим как

F(A,B)= {x|E(x)+E(x+α)=β, α ∈ A, β ∈ B} 

Как показано в [8], во многих случаях F(A,B) является смежным классом подпространства. Так же и в нашем случае. Более точно, имеется следующая лемма.

Лемма 1. Пусть Е является функцией раунда PRINTcipher исключающей дополнение начального ключа. α, U', U определены ранее. Тогда

F({α},U') = F(U',U) = U+c

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

Рис.4 показывает как различия в битах сокращенной дифференциальной характеристики из раздела 3 распространяются через функции раундов. Подчеркнутые значения являются позициями где распространение разницы имеет вероятность не равную 1. То есть, только эти позиции накладывают ограничения на пары, удовлетворяющие характеристике.

Это доказывает, что для ключа, не являющимся слабым, вероятность сокращенной дифференциальной характеристики равняется нулю, согласно предыдущей теореме. Для слабых ключей эта вероятность задаётся как Ek(U+d) = U+d, следовательно для любого x из Fa,b + k = U + d пара (x,x+a) удовлетворяет сокращенной дифференциальной характеристике полного раунда.

Статистическая атака и многомерная линейная атака

Как описано в [5], атака на PRINTcipher, обсуждаемая в разделе 2.2 сильно связана с статистической атакой. В этом разделе, после введения, в котором кратко описаны некоторые принципы статистической атаки, мы представим детали этой связи. Возможно, наиболее интересное открытие здесь заключается в том, что для PRINTcipher существует сильно смещенная линейная аппроксимации для любого количества раундов, если ключ слабый в отношении инвариантной подпространственной атаки. Такой вывод позволяет использовать связь между статистической атакой и многомерной линейной атакой (смотри 17]. Понимание такой сильно смещенной линейной аппроксимации, путем изучения линейной обертки является интересной задачей, которую мы оставим для предстоящего исследования.

Необходимая общая информация

Обозначения. Значения из Fn2 будем обозначать как , то есть

Рис.10.JPG

Мы заметили, что все линейные формы, то есть линейные функции : Fn2 F2 могут быть описаны как для подходящего a ∈ Fn2. Для заданной функции F: F2n F2m коэффициент Фурье на паре (a,b) ∈ F2n X F2m определяется как

Рис.9..JPG

Смещение єF(a,b) линейной аппроксимации для определяется как:

Рис.10.JPG

Фундаментальное отношение между преобразованием Фурье для функции F и смещением линейной аппроксимации задаётся как:

Рис.12.JPG

Статистическая атака Для начала вспомним некоторые концепции статистической атаки (более подробно в Baudoin Collard and Francois-Xavier Standaert. A statistical saturation attack against the block cipher PRESENT. In Marc Fischlin, editor, Proc. CT-RSA 2009, vol. 5473 of LNCS, p. 195{210. Springer, 2009.). Для заданной функции шифрования

:  F2n  F2n

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

:  F2r X F2s   F2t X F2u
 e(y,x) = (e(1)(y,x),e(2)(y,x))

где

r+s=t+u=n и (e(1)(y,x) ∈Ft2, e(2)(y,x) ∈Fu2.

Договоримся обозначать через hy ограничение e путем фиксирования битов с позиции r до позиции y и рассмотрения первых t выходных битов. Таким образом:

hy: Fs2    Ft2
hy(x) = e(1)(y,x)

Сложность статистической атаки зависит от емкости hy и обычно равна 1/Cap(hy). Расчет этой емкости является обычно довольно сложным([9].

Теорема 2 Средняя емкость статистической атаки, рассчитанная по всем возможным способам фиксирования вычисляется как:

Рис.13.JPG

Выбор значений зафиксированных битов

Рассмотрим случай, когда r = t, то есть, когда количество зафиксированных битов равно количеству полученных выходных битов. Предположим, что шифр уязвим для инвариантной подпространственной атаки. Как и для статистической атаки, сравнивая биективное линейное преобразование до и после шифрования мы можем предположить, что в случае слабого ключа аффинное подпространство вида {d} XFs2 отображено на аффинное подпространнство вида {d} XFs2. Это означает, что (в случае слабого ключа) функция ограничения hy при y=d является константой. То есть:

hd(x) = e(1)(d,x)=d

При правильном выборе значений фиксированных битов емкость максимальна. Таким образом, при слабом ключе правильное фиксирование битов приводит к оптимально статистической атаки. Обратите внимание, что Теорема 2 не говорит о существовании таких особых (правильных) случаев, она говорит лишь о средней емкости ограничений. Инвариантная подпространственная атака на PRINTcipher не означает, что PRINTcipher в общем уязвим для статистических атак, это неудивительно, если взять во внимание исследование[4]. Из него следует, что PRINTcipher устойчив к атакам такого рода.

Существование сильно смещенных аппроксимаций

Теорема 2 использовалась для расчета средней емкости с использованием коэффициентов Фурье. Отсюда следует:

Следствие 1. Предположим, что n-битный блочный шифр Ek уязвим для инвариантной подпространственной атаки, то есть существует подпространство U, константа d и ключи k такие что:

Ek(U+d) = U+d.

Далее, для ключей с существующей линейной аппроксимацией со смещением є, таким что:

є≥2dim(U)-n-1-22(dim(U)-n)-1.

Доказательство. Как доказано в разделе 4.2, hd является константной функцией. То есть

Cap(hd)=2r-1.

Кроме того:

Рис.14.JPG

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

Рис.15.jpg

Нижнюю границу максимального значения вычислим как:

Рис.16.JPG

Таким образом, существует как минимум один коэффициент Фурье, такой что:

Рис.17.JPG

Учитывая приведенные ранее равенства и учитывая, что r = n - dim U, теорема доказана. Данная теорема интересная только в случае, когда dim(U) > n/2, так как в таком случае существует аппроксимация. В противном случае она тривиальна. Подведем итог, приведя следующее следствие для PRINTcipher-48: Следствие 2. Для заданного слабого ключа при любом количестве раундов r ≤48 существует как минимум одна линейная аппроксимация для PRINTcipher-48 со смещением не менее 2-17-2-33.

Заключение

В работе была представлена новая атака против итеративных блочных шифров, названная инвариантная подпространственная атака и продемонстрирована ее применимость на примере взлома PRINTcipher по значимой части ключа. Представленная инвариантная подпространственная атака показывает, что 252 ключей (из 280) для PRINTcipher-48 и 2102 ключей (из 2160) для PRINTcipher-96 являются слабыми. Кроме того, мы показали связь между инвариантной подпространственной атакой и другими видами атак, такими как сокращенная дифференциальная атака, многомерная линейная атака и статистическая атака. На примере сокращенной дифференциальной атаки мы показали, что вероятность успешного взлома не зависит от раундов, что опровергает общеизвестное мнение, что вероятность успешного взлома зависит от вероятности в каждом раунде, и общая вероятность успеха взлома шифра может быть усреднена по всем ключам. Вероятность такой дифференциальной характеристики равна 2-16 для слабого ключа и 0 для не слабого заданного ключа в случае если количество раундов больше или равно двум. Кроме того, для PRINTcipher, существует сильно смещенная линейная аппроксимация для любого количества раундов, если задан слабый ключ. Например, существует по крайней мере одна линейная аппроксимация для PRINTcipher-48 со смещением не меньше 2-17.

Направление дальнейших исследований

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

Литература

1. Mohamed Ahmed Abdelraheem, Gregor Leander, and Erik Zenner. Differential cryptanalysis of round-reduced PRINTcipher: Computing roots of permutations. In Antoine Joux, editor, Proc. FSE 2011, vol. 6733 of LNCS. Springer, 2011.

2. Ishai Ben-Aroya and Eli Biham. Differential cryptanalysis of Lucifer. Journal of Cryptology, 9(1):21{34, 1996.

3. Andrey Bogdanov, Lars R. Knudsen, Gregor Leander, Christof Paar, Axel Poschmann, Matthew J. B. Robshaw, Yannick Seurin, and Charlotte Vikkels. PRESENT: An ultra-lightweight block cipher. In Pascal Paillier and Ingrid Ver- bauwhede, editors, Proc. CHES 2007, vol. 4727 of LNCS, p. 450{466. Springer, 2007.

4. Andrey Bogdanov and Christian Rechberger. A 3-subset meet-in-the-middle at- tack: Cryptanalysis of the lightweight block cipher KTANTAN. In Alex Biryukov, Guang Gong, and Douglas R. Stinson, editors, Proc. SAC 2010 vol. 6544 of LNCS, p. 229{240. Springer, 2011.

5. Christophe De Canniere, Orr Dunkelman, and Miroslav Knezevic. KATAN and KTANTAN - a family of small and efficient hardware-oriented block ciphers. In Christophe Clavier and Kris Gaj, editors, Proc. CHES 2009, vol. 5747 of LNCS, p. 272{288. Springer, 2009.

6. Joo Yeon Cho. Linear cryptanalysis of reduced-round PRESENT. In Josef Pieprzyk, editor, Proc. CT-RSA 2010, vol. 5985 of LNCS, p. 302{317. Springer, 2010.

7. Baudoin Collard and Francois-Xavier Standaert. A statistical saturation attack against the block cipher PRESENT. In Marc Fischlin, editor, Proc. CT-RSA 2009, vol. 5473 of LNCS, p. 195{210. Springer, 2009.

8. Baudoin Collard and Francois-Xavier Standaert. Multi-trail statistical saturation attacks. In Jianying Zhou and Moti Yung, editors, Proc. ACNS 2010, vol. 6123 of LNCS, p. 123{138, 2010.

9. Joan Daemen, Michael Peeters, Gilles Van Assche, and Vincent Rijmen. Nessie proposal: NOEKEON. http://gro.noekeon.org/Noekeon-spec.pdf, 2000.

10. Joan Daemen and Vincent Rijmen. Plateau characteristics. Information Security, IET, 1(1):11{17, 2007.

11. Itai Dinur and Adi Shamir. Breaking Grain-128 with dynamic cube attacks. In Antoine Joux, editor, Proc. FSE 2011, vol. 6733 of LNCS. Springer, 2011.

12. Carlo Harpes and James L. Massey. Partitioning cryptanalysis. In Eli Biham, editor, Proc. FSE 1997, vol. 1267 of LNCS, p. 13{27. Springer, 1997.

13. Deukjo Hong, Jaechul Sung, Seokhie Hong, Jongin Lim, Sangjin Lee, Bonseok Koo, Changhoon Lee, Donghoon Chang, Jaesang Lee, Kitae Jeong, Hyun Kim, Jongsung Kim, and Seongtaek Chee. HIGHT: A new block cipher suitable for low-resource device. In Louis Goubin and Mitsuru Matsui, editors, Proc. CHES 2006, vol. 4249 of LNCS, p. 46{59. Springer, 2006.

14. Simon Knellwolf, Willi Meier, and Maria Naya-Plasencia. Conditional differen- tial cryptanalysis of nlfsr-based cryptosystems. In Masayuki Abe, editor, Proc. Asiacrypt 2010, vol. 6477 of LNCS, p. 130{145. Springer, 2010.

15. Lars R. Knudsen, Gregor Leander, Axel Poschmann, and Matthew J. B. Robshaw. Printcipher: A block cipher for IC-Printing. In Stefan Mangard and Francois- Xavier Standaert, editors, Proc. CHES 2010, vol. 6225 of LNCS, p. 16{32, Springer, 2010.

16. Xuejia Lai, James L. Massey and Sean Murphy. Markov ciphers and differentail cryptanalysis. In Donald W. Davies, editor, Proc. Eurocrypt 1991, vol. 547 of LNCS, p. 17{38, Springer, 1991.

17. Gregor Leander. On Linear Hulls, Statistical Saturation Attacks, PRESENT and a Cryptanalysis of PUFFIN. In Kenneth G. Paterson, editor, Proc. Eurocrypt 2011, vol. 6632 of LNCS, p. 303{322, Springer, 2011.

18. Sean Murphy. The Effectiveness of the Linear Hull Effect. Technical report, RHUL- MA-2009-19, 2009.

Ссылки

  1. Mohamed Ahmed Abdelraheem, Gregor Leander, and Erik Zenner. Differential cryptanalysis of round-reduced PRINTcipher: Computing roots of permutations. In Antoine Joux, editor, Proc. FSE 2011, vol. 6733 of LNCS. Springer, 2011.
  2. Andrey Bogdanov and Christian Rechberger. A 3-subset meet-in-the-middle at- tack: Cryptanalysis of the lightweight block cipher KTANTAN. In Alex Biryukov, Guang Gong, and Douglas R. Stinson, editors, Proc. SAC 2010 vol. 6544 of LNCS, p. 229{240. Springer, 2011.
  3. Itai Dinur and Adi Shamir. Breaking Grain-128 with dynamic cube attacks. In Antoine Joux, editor, Proc. FSE 2011, vol. 6733 of LNCS. Springer, 2011.
  4. 4,0 4,1 Lars R. Knudsen, Gregor Leander, Axel Poschmann, and Matthew J. B. Robshaw. Printcipher: A block cipher for IC-Printing. In Stefan Mangard and Francois- Xavier Standaert, editors, Proc. CHES 2010, vol. 6225 of LNCS, p. 16{32, Springer, 2010..
  5. 5,0 5,1 Baudoin Collard and Francois-Xavier Standaert. A statistical saturation attack against the block cipher PRESENT. In Marc Fischlin, editor, Proc. CT-RSA 2009, vol. 5473 of LNCS, p. 195{210. Springer, 2009.
  6. Sean Murphy. The Effectiveness of the Linear Hull Effect. Technical report, RHUL- MA-2009-19, 2009..
  7. Xuejia Lai, James L. Massey and Sean Murphy. Markov ciphers and differentail cryptanalysis. In Donald W. Davies, editor, Proc. Eurocrypt 1991, vol. 547 of LNCS, p. 17{38, Springer, 1991..
  8. 8,0 8,1 8,2 8,3 Joan Daemen and Vincent Rijmen. Plateau characteristics. Information Security, IET, 1(1):11{17, 2007.
  9. Gregor Leander. On Linear Hulls, Statistical Saturation Attacks, PRESENT and a Cryptanalysis of PUFFIN. In Kenneth G. Paterson, editor, Proc. Eurocrypt 2011, vol. 6632 of LNCS, p. 303{322, Springer, 2011.