Атака на основе предположения байта-основы и детерминирования на SOSEMANUK

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 23:03, 24 января 2016.
A Byte-Based Guess and Determine Attack on SOSEMANUK[* 1]
0 A Byte-Based Guess and Determine Attack on SOSEMANUK.png
Авторы Xiutao Feng[@: 1],
Jun Liu[@: 2],
Zhaocun Zhou[@: 3],
Chuankun Wu[@: 4] and
Dengguo Feng[@: 5]
Опубликован 2010 г.
Сайт International Association for Cryptologic Research
Перевели Eugene Manaka[@: 6]
Год перевода 2015 г.
Скачать оригинал


Аннотация. SOSEMANUK - это программно-ориентированный поточный шифр, предложенный К. Бербэном и другими исследователями для проекта eSTREAM и вошедший в финальный вариант проекта. Было замечено, что большинство компонентов SOSEMANUK можно полагать байт-ориентированными. Следовательно злоумышленник может наблюдать SOSEMANUK с точки зрения, что единичный элемент – это байт вместо оригинального 32-битного слова. На основании вышеизложенной идее, в этой работе мы представляем новую атаку на основе предположения байта-основы и детерминирования на SOSEMANUK, где мы рассматриваем байт как основной блок данных и предполагаем некоторые определенные байты внутренним состоянием вместо целых 32-битных слов во время выполнения атаки. Как ни странно, нашей атаке нужно только несколько слов известного ключевого потока для восстановления всего внутреннего состояния SOSEMANUK и трудоемкость процесса может быть значительно снижена до O(). Поскольку SOSEMANUK имеет ключ с длиной от 128 до 256 бит, наши результаты показывают, что при длине ключа шифрования большей 176 бит наша атака на основе предположения байта-основы и детерминирования является более эффективной, чем перебор ключей.
Ключевые слова:eSTREAM, SOSEMANUK, атака на основе предположения и детерминирования.


Введение

Европейский eSTREAM[1] проект был запущен в 2004 году для рассмотрения потоковых шифров и закончился в 2008 году. Первоначально около 34 потоковых шифров-кандидатов было представлено в проекте eSTREAM, и после прохождения трех раундов 7 из них были отобраны. SOSEMANUK, предложенный К. Бербэном и другими исследователями[2], является одним из семи вышеупомянутых алгоритмов. SOSEMANUK - это программное обеспечение-ориентированной потоковый шифр, имеющий ключ с длиной, изменяющейся от 128 до 256 бит. Проект SOSEMANUK принял идеи как потокового шифра SNOW 2.0 [3], так и блочного шифра SERPENT [4], и нацелен на повышение в SNOW 2.0 как безопасности, так и эффективности.

Атака с помощью предположения и детерминирования является обычным нападением на потоковые шифры[5][6][7][8]. Основная идея нападения заключается в следующем: в первую очередь злоумышленник предполагает значения части внутренних состояний целевой алгоритма, затем атака займет немного ресурсов для вычисления значений всех остальных внутренних состояний алгоритма, используя значения предполагаемой части внутренних состояний и нескольких известных ключей потока. Когда значения всех внутренних состояний алгоритма установлены, злоумышленник проверяет правильность этих значений, производя потоки ключей с использованием ранее восстановленных значений, и сравнивая их с известными потоками ключей. Если потоки ключей совпали, это показывает, что восстановленные состояния правильны. Если потоки ключей не совпали, то злоумышленник повторяет вышеописанный процесс до тех пор, пока правильные внутренние состояния не будут найдены. Что касается SOSEMANUK, создатели SOSEMANUK[2] представили метод атаки с помощью предположения и детерминирования, сложность которого оценивалась как O (). В 2006 году Х. Ахмади и другими исследователями[9] пересмотрели атаку и снизили оценку трудоемкости до О (), и этот результат был дополнительно сокращен до O () Ю. Тсюноо и другими исследователями[10]. Недавно Лин и Цзе[11] дали новый результат, в котором они могли бы восстановить все внутренние состояния SOSEMANUK с временной сложностью O ().К сожалению, в их работе была допущена ошибка. На 1-ой стадии их атаки , , , и , , , были использованы для вывода ключевых слов , , , , а в 14-ом шаге , , , и , , , были использованы для вывода ключевых слов , , , . Однако, в соответствии с описанием SOSEMANUK выходные ключевые слова в следующем шаге следуют , , , , которые должны быть получены согласно , , , и , , , . Поэтому временную сложность они дали неправильно.

Известно, что большинство слов-ориентированных потоковых шифров сделало компромисс между безопасностью и эффективностью. С точки зрения исследователя, для выработки более эффективной реализации программного алгоритма некоторые определенные операторы, например исключающее ИЛИ, S-блоки, сложение по модулю , умножение или деление на примитивные элементы в конечной поле , где n может быть равно 8, 16 или 32, часто используются. Мы заметили, что большинство из этих операций может быть сделано на основе более мелких единиц, например, 16-битных слов или байтов. Поэтому с точки зрения злоумышленника, он может наблюдать за алгоритмом с точки зрения более мелкой единицы, а не оригинальных блоков слов. На основании вышеизложенной идее в этой работе мы представляем атаку на предположении байта-основы и детерменировании на SOSEMANUK, где мы рассматриваем байт в качестве основного блока данных и предполагаем некоторые определенные байты внутренних состояний, а не целых 32-битные слова в течение выполнение атаки. Неожиданно, но нашей атаке нужно только несколько известных потоков ключей, чтобы восстановить все внутренние состояния SOSEMANUK, и временная сложность может быть существенно снижена до O (). Это показывает, что, когда длина ключа шифрования больше 176 бит, атака на предположении и детерминировании является более эффективной, чем перебор ключей. Более того, наши результаты также показывают, что во время проектирования алгоритмов поточного шифрования необходимо сломать грань между различными операндами.

Остальная часть этой статьи организована следующим образом: в разделе 2 мы кратко напомним алгоритм SOSEMANUK, а в разделе 3 мы приведем основные свойства SOSEMANUK. В разделе 4 мы опишем все детали нашего нападения на SOSEMANUK. В разделе 5 мы дадим оценку информационной и временной сложностей нашей атаки. В разделе 6 даются дальнейшие обсуждение, а в разделе 7 делаем вывод.


Описание SOMEMANUK

В этом разделе мы кратко напомним алгоритм SOSEMANUK, все детали можно найти в [2].

SOSEMANUK - 32-битное слово-ориентированный потоковое шифрование, и логически состоит из трех частей: регистр сдвига с линейной обратной связью(РСЛОС), конечный автомат(КА) и циклическая функция Serpent1, см рис.1.

1 A Byte-Based Guess and Determine Attack on SOSEMANUK.png

Рис.1. Структура SOSEMANUK

РСЛОС

РСЛОС из SOSEMANUK определена над конечным полем , и содержит 10 32-битных регистров , 1 ≤ i ≤ 10. Обратный многчлен (x) РСЛОС определяется следующим образом:

где является корнем многочлена

над конечным полем , и является корнем двоичного многочлена.

Пусть последовательность генерируется РСЛОС. Тогда она удовлетворяет

КА

Нелинейная фильтрационная часть SOSEMANUK - конечный автомат(КА), который содержит два блока 32-битной памяти R1 и R2. В момент времени t, КА принимает значения , и регистров , и РСЛОС как входы, выходы 32-разрядного слова . Выполнение КА заключается в следующем:

где - сложение по модулю ; lsb(x) - младший бит ; равен , если , или равен , если ; внутренняя функция перехода Trans на 32-разрядных целых числах определяется:

где является левым циклическим оператором сдвига на 32-битовых строках

Циклическая функция Serpent1

В блочном шифровании SERPENT выполняются следующие этапы:

- начальная перестановка;
- S-бокс преобразование;
- линейное преобразование.

Здесь функция Serpent1 это один раунд SERPENT без начальной перестановки и линейного преобразования. S-бокс, используемый в Serpent1, - это S-box в SERPENT and работает в режиме bit-slice. Serpent1 берет выходы КА в четырех последовательных тактах входы, выходы четырех 32-битных слов , где , см. рис. 2.

2 A Byte-Based Guess and Determine Attack on SOSEMANUK.png

Рис.2. Циклическая функция Serpent1 в режиме bit-slice

Генерация потока ключей

Пусть , , , и , , , выходы РСЛОС и КА соответственно в последовательных тактах, начиная с момента времени , и , , , - ключевые слова, генерируемые SOSEMANUK в эти четыре последовательных такта. Тогда получаем:

Некоторые свойства SOSEMANUK

В этом разделе мы рассмотрим байт в качестве основного блока данных и опишем некоторые основные свойства SOSEMANUK с точки зрения байта-основы. Сначала введем некоторые обозначения.

Пусть - 32-битное слово. Обозначим - -ый байт , , то есть

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

Для различных 32-битных слов , слово может иметь различные значения в зависимости от контекста:

  1. Как операнд операции . Здесь - 32-битная строка и является побитовое исключающее ИЛИ.
  2. Как операнд целочисленного сложения или сложения по модулю , . Здесь обозначает целое число .
  3. Как элемент конечного поля . Здесь обозначает элемент в , где определяется из уравнения (1).

Теперь мы рассмотрим алгоритм SOSEMANUK с точки зрения байта-основы. Во-первых, заметим, что вычисление обратной связи РСЛОС (см. уравнение (2)) может быть представлено в форме байтов.

TemplateTheoremIcon.svg Теорема Лемма 1
Уравнение (2) может быть записана в байтовой форме следующим образом:
Доказательство
Из определения , мы получаем:

Отсюда следует, что

Пусть и . Тогда мы получаем

и

Объединив вышеуказанные уравнения и уравнение (2), и мы сразу получаем искомое.


Во-вторых, мы видим, что обновление R1 и выход конечного автомата и имеют следующие результаты:

TemplateTheoremIcon.svg Теорема Лемма 2
Уравнения (3) и (5) приведем по модулю для всех , то есть:

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

Доказательство
Без доказательства


Наконец, заметим, что циклическая функция Serpent1 имеют следующий вывод:

TemplateTheoremIcon.svg Теорема Лемма 3
Для любого , если значения k-ого бита каждого известны, то значения k-го бита каждого может быть рассчитано из определения Serpent1, передающего некоторый известный поток ключей, то есть

где

и , и - k-ые биты , и соответственно, . Аналогично, если i-ые байты каждого известны, то мы можем вычислить i-ые байты каждого .

Доказательство
Без доказательства


Выполнение атаки

В этом разделе мы всегда предполагаем, что часть ключевых слов поток {} имеют ZT наблюдается, где т = 1, 2, · · · N, N и достаточно большой для атаки на Работа. В этом разделе мы всегда предполагаем, что часть слов потока ключей была обнаружена, где , и является достаточно большим для атаки на работу. Для удобства обозначим через

вычет из согласно уравнению .

Перед описанием нападения, мы делаем следующее предположение:

Предположение 1.Младший бит равен 1, то есть,
Все описание атаки на SOSEMANUK можно разделить на пять этапов следующим образом.
Этап 1. Сначала предполагаем все значения 159 бит , , , , и оставшиеся значения 31 бита
Шаг 1.1Сначала делаем вывод о , , , и , следующих из:
Шаг 1.2 Подобно шагу 1.1 находим , , и , следующие из:
Шаг 1.3 Подобно шагу 1.2 делаем вывод о , , и , следующих их:
На этом этапе получили и
Этап 2.Так как мы получили и на 1-ом этапе, теперь из уравнения (7), мы можем вычислить и , то есть,
Кроме того, из уравнений и имеем
где , если , или в других случаях; и , если , или </math>c_{2} = 0</math>, если иначе.
Предполагая , мы имеем . Из этого следует, что
где , если , или , если иначе.
Объединив уравнения (8), (9), (10) и (11), имеем уравнение для переменной :
где и
В уравнении (12) все переменные кроме известны, поскольку встречается три раза в приведенном выше уравнении, легко проверить, что уравнение (12) имеет ровно одно решение. Обозначим это решение как . Когда было получено, мы находим , и из уравнений (8), (10) и (9) соответственно.
До этого момента мы получили и .
Этап 3.На этом этапе мы находим и , следующих из:
Этап 4. Мы предполагаем как , так и . Следующие выводы похожу с выводами из 1-ого этапа, и мы можем восстановить как , так и .
Этап 5. Наконец, мы находим , следующим из:

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

Процесс по вышеописанной атаке представлен в Таблице 1.

Таблица 1. Процесс атаки.
Предположение о
Шаги Предполагаемые внутренние состояния Определенные внутренние состояния Кол-во вариантов
Этап 1 .
Шаг 1.1 .
Шаг 1.2 .
Шаг 1.3 .
Этап 2 .
Этап 3 .
Этап 4 . .
Этап 5 .
обозначает 31 бит до второго значащего бита.

Временная и информационная сложности нашей атаки

При выполнении вышеуказанной атаки нужно угадать в общей сложности 175 бит внутренних состояний, в их числе 159 бит внутренних состояний на 1-ом этапе и 16 бит на 4-ом этапе, и затем все остальные внутренние состояния могут быть найдены при предположении . Поскольку вероятность равна , таким образом, временная сложность вышеописанной атаки на SOSEMANUK равна О().В атаке мы использовали только 8 слов известного потока ключей, и в ходе проверки нам нужно еще около 8 слов известного потока ключей для проверки правильности предполагаемых внутренних состояний. Так как сдвигая поток ключей по 4 словами, мы можем проверить два случая, то суммарная сложность данных составит около 20 слов известного потока ключей.

Дальнейшее обсуждение на предположении, Дальнейшее обсуждение на предположении, l s b ( R 1 1 ) = 1 {\displaystyle lsb(R1 {1})=1}

В приведенной выше атаке мы делаем предположение,что , которое гарантирует, что уравнение (12) на 2-ом этапе имеет ровно одно решение.Однако следует отметить, что это предположение не является необходимым для нашей атаки на работу алгоритма. На самом деле мы угадываем 160-битное значение и на 1-ом этапе. Когда , мы получаем на 2-ом этапе. Следовательно

где если , или , если иначе.

Подобно уравнению (12), объединив уравнения (8), (9), (10) и (11 '), мы имеем уравнение для переменной :

где и . Так как дважды встречается в уравнении (), легко проверить, что уравнение () либо не имеет решений, либо имеет решений для некоторого неотрицательного целого числа k. Когда уравнение () не имеет решений, мы вернемся к 1-ому этапу и повторим подбор новых значений внутренних состояний. Когда уравнение () имеет решений для некоторого целого , запишем все решения, а затем для каждого решения мы используем дедукцию в соответствии с 3-им, 4-ым и 5-ым этапами. Наконец, мы получаем различных значений внутренних состояний SOSEMANUK и проверяем их правильность.

Теперь оценим сложности вышеуказанным способом. На 1-ом этапе мы предполагаем 160-битовое значение внутренних состояний вместо 159-битные значения. из этих значений удовлетворяют и оставшиеся удовлетворяют . Относительно значений, удовлетворяющих мы получаем возможных значений и после 2-ого этапа. Относительно значений, удовлетворяющих , так как уравнение () имеет столько же решений, сколько имеется возможных значений переменных, когда все переменные, кроме , принимают все возможные значения, то мы получаем также возможных значений s и после 2-ого этапа. Поэтому мы получаем возможных значений. Для каждого возможного значения мы используем дедукцию в соответствии с 3-им, 4-ым и 5-ым этапами, следовательно, общая трудоемкость по-прежнему O (). Но без предположения сложность данных сводится к 16 слов известного потока ключей.

Вывод

В этой статье мы представили атаку на основе предположения байта-основы и детерминирования на SOSEMANUK, которой нужно только несколько слов потока ключей, чтобы восстановить все внутренние состояния SOSEMANUK с временной сложностью O (). Результаты показывают, что когда длина ключа шифрования больше, чем 176 бит, атаку на основе предположения и детерминирования является более эффективной, чем перебор ключей.

Благодарности

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

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

  1. State Key Laboratory of Information Security, Institute of Software, Chinese Academy of Sciences, Beijing, 100190, China, E-mail: fengxt@is.iscas.ac.cn
  2. State Key Laboratory of Information Security, Institute of Software, Chinese Academy of Sciences, Beijing, 100190, China, E-mail: liuj@is.iscas.ac.cn
  3. State Key Laboratory of Information Security, Institute of Software, Chinese Academy of Sciences, Beijing, 100190, China, E-mail: zhouzc@is.iscas.ac.cn
  4. State Key Laboratory of Information Security, Institute of Software, Chinese Academy of Sciences, Beijing, 100190, China, E-mail: ckwu@is.iscas.ac.cn
  5. State Key Laboratory of Information Security, Institute of Software, Chinese Academy of Sciences, Beijing, 100190, China, E-mail: feng@is.iscas.ac.cn
  6. Eugene Manaka, Bauman Moscow State Technical University, IU-8, E-mail: djon126@mail.ru

Примечания

  1. Эта работа была поддержана Национальным фондом естественных наук (грант № 60833008 и 60902024)

Литература

  1. The eSTREAM project, http://www.ecrypt.eu.org/stream/
  2. 2,0 2,1 2,2 C. Berbain, O. Billet, A. Canteaut, N. Courtois, H. Gilbert, L. Goubin, A. Gouget, L. Granboulan, C. Lauradoux, M. Minier, T. Pornin and H. Sibert, SOSEMANUK, a fast software-oriented stream cipher, eSTREAM, the ECRYPT Stream Cipher Project, Report 2005/027, 2005.
  3. P. Ekdahl and T. Johansson, A new version of the stream cipher SNOW, In Selected Areas in Cryptography–SAC2002, LNCS 2295, pp.47-61, 2002.
  4. R. Anderson, E. Biham, and L.R. Knudsen, Serpent: A proposal for the advanced encryption standard, NIST AES Proposal, 1998.
  5. D. Bleichenbacher and S. Patel, SOBER cryptanalysis, Fast Software Encryption,FSE’99, LNCS1636, pp.305-316, 1999.
  6. P. Hawkes and G. Rose, Exploiting multiplies of the connection polynomial in word-oriented stream ciphers, ASIACRYPT2000, LNCS1976, pp.302-316, 2000.
  7. P. Hawkes and G. Rose, Guess and determine attacks on SNOW, In Selected Area of Cryptography–SAC2002, LNCS 2595, pp.37-46, 2002.
  8. C.D. Canniere, Guess and determine attacks on SNOW, NESSIE Public Document,NES/DOC/KUL/WP5/011/a, 2001.
  9. H. Ahmadi, T. Eghlidos and S. Khazaei, Improved guess and determine Attack on SOSEMANUK, Tehran, Iran, 2006,http://www.ecrypt.eu.org/stream/sosemanukp3.html.
  10. Y. Tsunoo, T. Saito, M. Shigeri, T. Suzaki, H. Ahmadi, T. Eghlidos and S. Khazaei, Evaluation of SOSEMANUK with regard to guess-and-determine attacks, 2006, http://www.ecrypt.eu.org/stream/sosemanukp3.html.
  11. D. Lin, G. Jie, Guess and Determine Attack on SOSEMANUK, 2009 Fifth International Conference on Information Assurance and Security, vol.1, pp.658-661, 2009.