Условный дифференциальный криптоанализ систем на основе РСНЛОС

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 13:05, 2 декабря 2015.
Conditional Differential Cryptanalysis of NLFSR-based Cryptosystems
Two-Output Secure Computation with Malicious Adversaries.png
Авторы Simon Knellwolf, Willi Meier, Mar´ıa Naya-Plasencia FHNW, Switzerland
Опубликован 2010 г.
Сайт Department of Computer Science
Перевели Egor Zorin, Arseniy Kolobaev
Год перевода 2015 г.
Скачать оригинал

Аннотация:
Регистры сдвига с нелинейными обратными связями широко используются при реализации легковесных криптографических примитивов. Мы предлагаем общую методику оценки стойкости подобных структур, основанную на дифференциальном криптоанализе. Основная идея заключается в определении ограничений на внутреннее состояние, позволяющих получить разностную характеристику для большого числа раундов. В зависимости от того, затрагивают ли эти ограничения только открытые параметры, или также ключевые переменные, строятся атаки различения и частичного восстановления ключа. Разработанные методы применяются для анализа стойкости алгоритма Grain v1, вышедшего в финал конкурса eSTREAM, а также семейства блочных шифров KATAN/KTANTAN.

Методика позволяет построить атаку различения на алгоритм Grain, усеченный до 104 из 160 раундов, и получить некоторые сведения о ключе. Она естественным образом расширяется на дифференциалы высшего порядка, что дает возможность провести атаку различения на алгоритм Grain-128, усеченный до 215 из 256 раундов, и извлекать информацию о ключе до 213 раундов. Указанные атаки являются лучшими из известных на данный момент и осуществимы на практике за приемлемое время.

Ключевые слова:

  • дифференциальный криптоанализ
  • РСНЛОС
  • атака различения
  • восстановление ключа
  • Grain
  • KATAN/KTANTAN

Введение

Для обеспечения безопасности сред с ограниченными вычислительными ресурсами, таких как радиочастотные метки и сенсорные сети, был разработан ряд криптографических примитивов, в том числе поточные и легковесные блочные шифры. К подобным алгоритмам относятся поточные шифры Trivium [1] и Grain [2] [3], включенные в профиль перспективных поточных шифров для систем с ограниченными ресурсами конкурса eSTREAM [4], и семейство блочных шифров KATAN/KTANTAN [5]. Основным элементом указанных алгоритмов являются регистры сдвига с нелинейными обратными связями (РСНЛОС), которые, с одной стороны, обеспечивают эффективность аппаратной реализации, а с другой—позволяют противостоять алгебраическим атакам.

Как поточные, так и блочные шифры используют секретный ключ и открытый параметр (вектор инициализации для поточных и открытый текст для блочных шифров) для выработки ключевого потока или шифртекста посредством криптографического преобразования. В криптоанализе такие системы часто рассматриваются как наборы булевых уравнений, связывающих пару значений ключа и открытого параметра с битами выхода , при этом ряд методов строится на анализе производных функции . Указанные методы могут быть грубо разделены на алгебраические и статистические. Кубическая атака [6] относится к алгебраическим методам: она заключается в нахождении множества производных , линейных по битам ключа, и восстановлении ключа путем решения системы линейных уравнений. Тест -одночленов [7] предоставляет статистический аппарат для анализа распределения одночленов степени в алгебраической нормальной форме . Еще один статистический подход, описанный в [8], [9], заключается в применении понятия нейтральных битов ключа к производным . Концепция кубических тестеров, введенная в [10], использует многие из этих методов. Общей чертой упомянутых подходов является то, что в них функция рассматривается в виде черного ящика и структура криптографического примитива используется только косвенным образом.

В этой работе описывается общий метод анализа, который мы назвали условным дифференциальным криптоанализом. Он состоит в изучении частот значений производных для специальным образом подобранных открытых текстов (или векторов инициализации). Метод дифференциального криптоанализа, предложенный в [11] для анализа блочных шифров, основывается на изучении распространения разностей входных данных по итеративной структуре. В настоящее время этот метод также широко используется для анализа механизмов инициализации поточных шифров (см. [12], [13], [14]). В случае РСНЛОС на каждой итерации изменяется лишь несколько бит внутреннего состояния, а остальные биты просто сдвигаются, что приводит к относительно медленному рассеиванию. Основываясь на методиках модификации сообщений, использованных в [15] для криптоанализа хеш-функций, мы отслеживаем изменения раунд за раундом и выявляем условия на биты исходного состояния, предотвращающие распространение изменений на начальных итерациях. С учетом этих условий строятся открытые тексты (или векторы инициализации), обладающие одинаковой характеристикой на начальных раундах и позволяющие выявить отклонения в разности выходных значений. В некоторых случаях условия затрагивают также определенные биты ключа, что позволяет осуществить атаку его частичного восстановления.

Общую идею условного дифференциального криптоанализа необходимо дорабатывать и приспосабливать отдельно для каждого криптографического примитива, что и было сделано для семейства блочных шифров KATAN и его аппаратно-оптимизированного варианта KTANTAN, а также для поточных шифров Grain v1 и Grain-128. Анализ шифров KATAN/KTANTAN основывается только на производных первого порядка и хорошо иллюстрирует наш подход. Для усеченного до 78 из 254 раундов шифра KATAN32 мы можем восстановить как минимум два бита ключа с близкой к единице вероятностью и сложностью 222. Схожие результаты были получены и для других шифров того же семейства. Следует отметить, что нам не известны предыдущие работы по криптоанализу KATAN/KTANTAN. Анализ Grain v1 строится по схожей схеме, однако при этом используются более сложные соотношения. Нами проведена атака различения на алгоритм, включающий до 104 из 160 раундов. Та же атака может быть использована для восстановления одного ключа и четырех линейных соотношений на его биты с высокой степенью вероятности. Предыдущий анализ шифра был проведен в работе [13], в которой свойства слайдинга используется для ускорения полного перебора в два раза, и в работе [16], в которой неслучайность прослеживается до 81 раунда.

Условный дифференциальный криптоанализ естественным образом расширяется на производные высших порядков. Это демонстрируется нашей атакой на Grain-128, который, как ни странно, является более уязвимым к подобному анализу. Нам удалось осуществить атаку различения для 215 из 256 раундов и различные атаки восстановления ключа для немного меньшего числа раундов. Для 197 раундов мы восстанавливаем восемь бит ключа с вероятностью до 0,87, а для 213 раундов — два бита с вероятностью до 0,59. Ранее известные результаты описывали теоретическую атаку восстановления ключа на алгоритм со 180 раундами и позволяли ускорить полный перебор в 24 раз, но не позволяли восстановить значения отдельных ключевых битов (см. [8]). Кроме того, в работе [13] упоминается восстановление ключа для модификации алгоритма, включающей до 192 раундов, а в [16] были обнаружены отклонения от случайности при подобранных ключах.

Работа организована следующим образом. В разделе 2 приводится определение производных высшего порядка для булевых функций и рассматривается применение к ним частотных тестов. В разделе 3 рассматривается общая идея условного дифференциального криптоанализа систем, основанных на РСНЛОС. Разделы 4, 5 и 6 посвящены адаптации указанного метода и его применению для анализа шифров семейства KATAN/KTANTAN, Grain v1 и Grain-128.

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

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

Далее мы напомним определение -ой производной булевой функции, введенное в [17], [18], и рассмотрим применение частотного теста к таким производным.

Производные булевых функций

Пусть булева функция. Тогда производной по направлению называется булева функция

.

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

.

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

Случайные булевы функции и частотный тест

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

приблизительно следует стандартному нормальному распределению. Обозначим через

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

.

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

Частотный тест для производных

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

Условный дифференциальный криптоанализ РСНЛОС

В этом разделе приводится основная идея нашего метода. Она основывается на методах модификации сообщений, предложенных в [15] для ускорения поиска коллизий в хеш-функциях. Мы отслеживаем распространение разностей во входных данных по криптосистеме на основе РСНЛОС и по возможности используем нелинейность обратной связи для предотвращения такого распространения, что достигается за счет определения ограничений на переменные внутреннего состояния. Атака с выбранным открытым текстом различается в зависимости от того, включают ли эти ограничения только открытый параметр или также биты секретного ключа. Целью является подбор большого числа входных данных, удовлетворяющих ограничениям, т. е. имеющим одинаковую разностную характеристику на начальных раундах. Другими словами, мы анализируем производные булевых функций с ключом и используем тот факт, что их выход вычисляется итеративно.

Далее мы кратко рассмотрим криптосистемы на основе РСНЛОС и поясним, почему к ним применима наша методика анализа. Затем мы определим три типа условий, ограничивающих распространение разностей в указанных криптосистемах, и покажем, как строить атаку по выбранному открытому тексту (выбранному вектору инициализации) в каждом случае. В последующих разделах общая методика будет адаптирована для построения конкретных атак на алгоритмы KATAN/KTANTAN, Grain v1 и Grain-128

Криптосистемы на основе РСНЛОС

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

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

Условия и их классификация

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

тип 0: условия включают только биты ;
тип 1: условия включают биты и ;
тип 2: условия включают только биты .

В атаках с выбранным открытым текстом (выбранным вектором инициализации), атакующая сторона легко может удовлетворить условия типа 0; в то же время она абсолютно не способна влиять на выполнение условий типа 2. В большинстве случаев условия типа 2 содержат простые соотношения, вероятность выполнения которых для случайно и равновероятно выбранного ключа можно легко определить. Поскольку мы не предполагаем, что наша атака может быть проведена на более чем одном ключе, условия типа 2 в общем случае снижают преимущество атак различения, а также порождают классы слабых ключей относительно такого рода атак. С другой стороны, мы используем условия типа 2 для построения атак восстановления ключа на основе проверки статистических гипотез. Более подробно этот вопрос рассматривается при криптоанализе Grain-128 в разделе 6.

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

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

Выбор разностей

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

Множество разностей для производных высшего порядка можно построить путем комбинации производных первого порядка, характеристики которых не влияют друг на друга на начальных раундах. В работе [16] описан генетический алгоритм нахождения подходящего набора разностей для безусловной модели анализа. Использованный подход черного ящика привел к построению каких-либо особенно хороших множеств для условного анализа

Анализ KATAN/KTANTAN

KATAN/KTANTAN представляет собой семейство легковесных блочных шифров, предложенных в [5]. Оно состоит из шести алгоритмов, обозначаемых KATANn и KTANTANn, где n = 32, 48, 64—размер блока шифрования. Во всех вариан- тах шифра используется 80-битный ключ, а в качестве примитивов используются два регистра сдвига с нелинейными обратными связями и один небольшой регистр сдвига с линейными обратными связями (РСЛОС), играющий роль счетчика. Единственное различие между алгоритмами KATANn и KTANTANn заключается в процедуре расписания ключей.

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

Особо отметим, что наши исследования не обнаружили какой-либо слабости в шифрах KATAN/KTANTAN. Напротив, его результаты свидетельствуют о достаточно большом количестве раундов для обеспечения запаса по стойкости.

Описание KATAN32

В шифре KATAN32 используются два РСНЛОС длины 13 и 19 бит, внутренние состояния которых мы будем обозначать через и соответственно. 32-разрядный блок открытого текста загружается в регистры путем записи , и . РСЛОС имеет длину 8 бит, и его внутренне состояние мы обозначим через . Начальными значениями РСЛОС являются для и . Полный цикл шифрования включает 254 раунда, каждый из которых описывается соотношениями

где - биты ключа и вычисляются рекурсивно по формуле

для . После завершения процедуры состояние РСНЛОС является шифртекстом. При рассмотрении усеченной модификации алгоритма с раундами в качестве шифртекста используются значения , и .

Атака восстановления ключа на 78-раундовую версию KATAN32

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

Мы рассматриваем разность веса 5 для битов 1, 7, 12, 22 и 27 блока открытого текста. Пусть - исходная разность. Для раунда 0 справедливо

поэтому для ограничения распространения изменений налагаются условия и . Аналогично из соотношений для раундов 1, 2, 3 и 5 требуется, чтобы биты имели нулевое значение. На раунде 7

и мы накладываем первое условие типа 1:

Для раунда 9 используется условие . Три дополнительные условия типа 1 следуют из соотношений для раундов 11, 13 и 20:

Свободные биты для указанных условий можно напрямую определить из уравнений. К ним относятся:

и .

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

совместна для фиксированных A, B, C. Указанная система имеет различных решений, которые могут быт добавлены к каждому допустимому открытому тексту, что в общей сложности дает возможность породить набор из допустимых открытых текстов на основании одного. Поскольку мы наложили 9 условий типа 0, существует различных наборов открытых текстов для каждого ключа. Условия истинны для хотя бы одного набора, и на нем разность значений бита 18 шифртекста после 78 раундов (т. е. бита ) сильно отклоняется от равномерного распределения. Мы применяем частотный тест значений для каждого из полученных наборов открытых текстов. При уровне значимости тест дает отрицательный результат с близкой к единице вероятностью для хотя бы одного набора, и для него с близкой к единице вероятностью все четыре условия типа 1 выполнены. Это позволяет с высокой вероятностью восстановить значения , соотношение и либо значение (если ), либо соотношение . Сложность атаки составляет .

Анализ KATAN48 и KATAN64

Все три члена семейства KATAN выполняют шифрование за 254 раунда. РСЛОС и алгебраическая структура нелинейных обратных связей РСНЛОС также одинаковы. Различия между шифрами KATANn заключаются в размере блока n, длине и позициях съема РСНЛОС, а также в количестве обновлений состояния РСНЛОС в течение одного раунда.

В шифре KATAN48 используются РСНЛОС длины 19 и 29 бит, обновляющиеся дважды на каждом раунде. Наилучшие результаты были получены нами при разности веса 4 для битов 1, 10, 19 и 28 открытого текста. Наложив четыре условия типа 0 и два условия типа 1, мы можем получить набор мощности для каждого допустимого открытого текста, что позволяет восстановить бит ключа и соотношение после 70 раундов (140 обновлений РСНЛОС) со сложностью .

В шифре KATAN64 длины РСНЛОС составляют 25 и 39, а количество обновлений - три на каждом раунде. Наилучшие результаты получены для разности веса три (биты 0, 13 и 26). При шести условиях типа 0 и двух условиях типа 1 мощность набора составляла не менее для каждого допустимого открытого текста. Атака позволяет восстановить и после 68 раундов (204 обновлений РСНЛОС) со сложностью .

Анализ семейства KTANTAN

Шифры KTANTANn очень схожи с KATANn. Различия заключаются только в используемой процедуре расписания ключей. В шифрах семейства KATAN ключ загружается в регистр сдвига, и начиная с раунда 40 раундовые ключи получаются линейным расширением исходного. До раунда 40 в качестве раундовых ключей используются биты оригинального ключа. В KTANTAN начиная с первого раунда раундовые ключи являются линейной комбинацией битов исходного ключа (зависящей от целиком известного состояния счетчика РСЛОС). Таким образом, наш анализ KATANn напрямую переносится на KTANTANn, однако вместо восстановления битов ключа восстанавливаются значения их линейных комбинаций. Например, для KATAN32 восстанавливается значение суммы вместо бита .

Анализ Grain v1

Шифр Grain v1 был предложен в работе [3] и отобран в качестве финалиста в портфолио конкурса eSTREAM [4]. В нем используется 80-битный ключ и 64-битный вектор инициализации . Шифр включает три структурных элемента: 80-битный РСЛОС, 80-битный РСНЛОС и нелинейную функцию выхода. Состояние РСЛОС и РСНЛОС мы будем обозначать через и соответственно. В качестве начальных значений регистров используются для и для , а обратные связи описываются соотношениями

где линейна, а степень равна 6. Функция выхода имеет вид

где и

Перед шифрованием выполняется 160 холостых циклов без выработки выходной последовательности, при этом значение функции выхода через обратную связь подается на вход РСЛОС и РСНЛОС.

При рассмотрении усеченного варианта шифра Grain v1 с раундами инициализации функционирование указанной обратной связи ограничено раундами и первым битом выхода шифра считается значение .

Подход к анализу аналогичен использованному для шифра KATAN32, однако уравнения для условий являются более сложными. Сначала мы проведем атаку на 97 раундов алгоритма, а затем расширим ее до 104 раундов.

Атака различения и восстановление ключа для 97 раундов

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

Мы налагаем условие типа 0 и определяем условия типа 1 , чтобы предотвратить распространение. Следующие условия определяются на раунде 34, для которого

откуда следуют условия и . Аналогично на раундах 40 и 46 получаются условия и . Таким образом, мы наложили одно условие типа 0 на раунде 12 и пять условий типа 1 на раундах 12, 34, 40 и 46. Существует 25 свободных битов для условий типа 1:

и

В среднем ожидается, что один из случайно выбранных векторов инициализации удовлетворяет сформулированным условиям. Мы строим различитель, который случайно выбирает векторов инициализации и для каждого из них применяет частотный тест значения на наборе мощности , порожденном свободными битами. Вместо случайного выбора векторов инициализации можно выбрать и для каждого из них положить и , что гарантирует выполнения условия раунда 12 в одном из случаев. Эксперименты, проведенные на ключевом множестве мощности при уровне значимости , показали, что хотя бы один из тестов дает отрицательный результат с вероятностью 0,99. Полученные результаты соответствуют различителю со сложностью и преимущество около 0,83 для усеченного до 97 раундов шифра Grain v1.

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

Расширение на 104 раунда

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

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

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

Мощность набора векторов инициализации можно увеличить еще больше, поскольку несвободные биты и должны удовлетворять только линейному уравнению. Это позволяет построить различитель и преимуществом около 0,58.

Примечания

  1. В оригинале distinguishing advantage (прим. пер.)

Литература

  1. Canni`ere, C.D.: Trivium: A Stream Cipher Construction Inspired by Block Cipher Design Principles. In: Katiskas, S.K., L´opez, J., Backes, M., Gritzalis, S. Preneel, B. (eds.) ISC 2006. LNCS, vol. 4176, pp. 171–186. Springer, Heidelberg (2006)
  2. Hell, M., Johansson, T., Maximov, A., Meier, W.: A Stream Cipher Proposal: Grain-128. In: ISIT, pp. 1614–1618 (2006)
  3. 3,0 3,1 Hell, M., Johansson, T., Meier, W.: Grain: A Stream Cipher for Constrained Environments. IJWMC 2(1), 86–93 (2007)
  4. 4,0 4,1 ECRYPT: The eSTREAM Project, http://www.ecrypt.eu.org/stream/
  5. 5,0 5,1 Canni`ere, C.D., Dunkelman, O., Knezevic, M.: KATAN and KTANTAN—A Family of Small and Efficient Hardware-Oriented Block Ciphers. In: Clavier, C., Gaj, K. (eds.) CHES 2009. LNCS, vol. 5747, pp. 272–288. Springer, Heidelberg (2009)
  6. Dinur, I., Shamir, A.: Cube Attacks on Tweakable Black Box Polynomials. In: Joux, A. (ed.) EUROCRYPT 2009. LNCS, vol. 5479, pp. 278–299. Springer, Heidelberg (2010)
  7. Englund, H., Johansson, T., Turan, M. S.: A Framework for Chosen IV Statistical Analysis of Stream Ciphers. In: Srinathan, K., Rangan, C.P., Yung, M. (eds.) INDOCRYPT 2007. LNCS, vol. 4859, pp. 268–281. Springer, Heidelberg (2007)
  8. 8,0 8,1 Fischer, S., Khazaei, S., Meier, W.: Chosen IV Statistical Analysis for Key Recovery Attacks on Stream Ciphers. In: Vaudenay, S. (ed.) AFRICACRYPT 2008. LNCS, vol. 5023, pp. 236–245. Springer, Heidelberg (2008)
  9. Khazaei, S., Meier, W.: New Directions in Cryptanalysis of Self-Synchronizing Stream Ciphers. In: Chowdhury, D.R., Rijmen, V., Das, A. (eds.) INDOCRYPT 2008. LNCS, vol. 5365, pp. 15–26. Springer, Heidelberg (2008)
  10. Aumasson, J. P., Dinur, I., Meier, W., Shamir, A.: Cube Testers and Key Recovery Attacks on Reduced-Round MD6 and Trivium. In: Dunkelman, O. (ed.) Fast Software Encryption. LNCS, vol. 5665, pp. 1–22. Springer, Heidelberg (2009)
  11. Biham, E., Shamir, A.: Differential Cryptanalysis of DES-like Cryptosystems. In: Menezes, A., Vanstone, S.A. (eds.) CRYPTO 1990. LNCS, vol. 537, pp. 2–21. Springer, Heidelberg (1991)
  12. Biham, E., Dunkelman, O.: Differential Cryptanalysis in Stream Ciphers. Cryptology ePrint Archive, Report 2007/218 (2007), http://eprint.iacr.org/
  13. 13,0 13,1 13,2 Canni`ere, C.D., K¨u¸c¨uk, ¨ O., Preneel, B.: Analysis of Grain’s Initialization Algorithm. In: Vaudenay, S. (ed.) AFRICACRYPT 2008. LNCS, vol. 5023, pp. 276–289. Springer, Heidelberg (2008)
  14. Wu, H., Preneel, B.: Resynchronization Attacks on WG and LEX. In: Robshaw, M. J.B. (ed.) FSE 2006. LNCS, vol. 4047, pp. 422–432. Springer, Heidelberg (2006)
  15. 15,0 15,1 Wang, X., Yu, H.: How to Break MD5 and Other Hash Functions. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 19–35. Springer, Heidelberg (2005)
  16. 16,0 16,1 16,2 Aumasson, J. P., Dinur, I., Henzen, L., Meier, W., Shamir, A.: Efficient FPGA Implementations of High-Dimensional Cube Testers on the Stream Cipher Grain-128. In: SHARCS (2009)
  17. Knudsen, L.R.: Truncated and Higher Order Differentials. In: Preneel, B. (ed.) FSE 1994. LNCS, vol. 1008, pp. 196–211. Springer, Heidelberg (1995)
  18. Lai, X.: Higher order derivatives and differential cryptanalysis. In: Blahut, R.E., Costello, D. J., Maurer, U., Mittelholzer, T. (eds.) Communicationis and Cryptography: Two Sides of one Tapestry, pp. 227–233. Kluwer Academic Publishers, Dordrecht (1994)