Decim

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

В криптографии, Decim — потоковый шифр на основе РСЛОС, разработанный Комом Бербаином, Оливером Биллетом, Анн Канту, Николя Куртуа, Бландином Дебре, Генри Гильбертом, Луи Губином, Алином Гуже, Луи Гранбуланом, Седериком Ларду, Марин Минье, Томасом Порнином и Эрвом Сибе. Специализирован для аппаратной реализации. Запатентован. Был представлен в проекте eSTREAM, где не прошёл дальше третьего этапа.

Генерация ключевого потока шифром Decim

Самое главное требование к шифрам — устойчивость к различным видам атак. Алгебраические атаки — одна из самых серьёзных угроз безопасности потоковым шифрам. Если соотношение между комбинацией битов секретного ключа и порождённым её битом гамма является простым или легко предсказуемым, то и нахождение алгебраических зависимостей между комбинацией битов секретного ключа и битом ключевого потока (гамма) так же является простой задачей. Для усложнения соотношений между комбинацией битов секретного ключа (или комбинацией битов начального состояния РСЛОС, порождённого секретным ключом) и битов ключевого потока (гамма) используют нелинейную фильтрующую функцию от комбинации битов секретного ключа и механизмы десинхронизации между комбинацией битов секретного ключа и битами ключевого потока (гамма). Оба этих механизма (нелинейная фильтрующая функция и механизм десинхронизации между комбинацией битов РСЛОС и битами ключевого потока) являются основой работы и основным средством предотвращения криптоаналитических атак шифра Decim.

Обзор работы Decim

[править | править код]

Начало работы потокового шифра Decim начинается с ввода 80-битного секретного ключа и 64-битного открытого ключа (Initialization Vector). Затем, с помощью определённых линейных комбинаций битов и битов , использования нелинейной фильтрующей функции и применения механизма выборки ABSG вычисляется начальное состояние 192-битного РСЛОС. После выполнения всех этих операций начинается генерация ключевого потока [1] и заполнение им специального буфера BUFFER, использующегося для обеспечения непрерывной выдачи битов на выход шифра, где происходит их сложение по модулю два с двоичной последовательностью символов открытого текста.

Спецификация

[править | править код]

Примитивный многочлен, ассоциированный с РСЛОС, имеет вид:

Обозначим через [2] последовательность битов, полученных с выхода РСЛОС, тогда правило вычисления бита на выходе РСЛОС имеет вид:

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

и

, где

Пусть

.

Позиции битов РСЛОС, которые являются аргументами и :

  • для : 1, 32, 40, 101, 164, 178, 187;
  • для : 6, 8, 60, 116, 145, 181, 191.

Тогда

.

Механизм выборки ABSG

[править | править код]

Механизм выборки ABSG используется для предотвращения алгебраических атак и некоторых видов быстрых корреляционных атак с помощью десинхронизации фильтрованных битов РСЛОС и битов гамма . Работа механизма выборки ABSG заключается в разбивке последовательности на подпоследовательности вида , где , и выдачи , если , и в другом случае.

Алгоритм работы ABSG

Input: ()

Set: ,

Repeat the following steps:

  1. , ;
  2. ;
  3. while (==) ;
  4. ;
  5. output ;
  6. ;

Пример:

пусть , тогда, соответствующая последовательность на выходе ABSG имеет вид .

В среднем, бит, поступившем на вход ABSG, соответствует бит на выходе, что и видно из примера.

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

После инициализации начального состояния РСЛОС, начинается заполнение BUFFER, и только после того, как BUFFER будет заполнен начнётся шифрование открытого текста (причём BUFFER работает по типу очереди — первый бит попавший в BUFFER, первым и выходит).

Существует вероятность, что в то время как BUFFER должен выдать бит, он оказался пустым. Эта вероятность мала, например, для BUFFER с четырьмя входами, вероятность, что он оказался пуст, в то время как он должен выдать бит, равна . Разработчики Decim предлагают не считаться с этой возможностью, принимая, что её вероятность равна нулю.

Инициализация начального состояния РСЛОС

[править | править код]

Сектретный ключ имеет длину 80 бит, открытый ключ (Initialization Vector) имеет длину 64 бита, но дополняется нулями до 80 бит. Пусть биты РСЛОС. Тогда начальное состояние РСЛОС вычисляется следующим образом:

Видно, что число всевозможных начальных состояний РСЛОС это .

Некоторые пояснения работы Decim

[править | править код]

Для предотвращения атак компромисс «время-память» длина РСЛОС должна быть не меньше 160 бит. Также РСЛОС должен быть прост в аппаратной реализации. Исходя из этих факторов, размер РСЛОС был выбран равным 192 битам.

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

Фильтрующая функция должна быть равновесной[3] и для предотвращения дифференциального криптоанализа должна удовлетворять propagation criterion: функция должна быть равновесной. Также, для упрощения аппаратной реализации, желательно, чтобы функция была симметричной, то есть, чтобы значение функции зависело только от веса Хэмминга её аргумента (набора x_1,…x_7). Всем этим требованием удовлетворяет квадратичная функция вида:

,

которая и используется, как фильтрующая функция шифра Decim.

Надёжность шифра Decim

[править | править код]

Исключая сложные случаи атак компромисс «время-память» вычислительная сложность атак на шифр Decim, по мнению его авторов, равна сложности атаки методом грубой силы и составляет не меньше, чем [4].

Но, независимый криптоанализ, проведенный Хунян Ву и Бартом Пренилом, показал ненадежность шифра Decim, причём вычислительная сложность атаки оказалась не больше чем , что является абсолютно неприемлемым[5].

Примечания

[править | править код]
  1.  — гамма, сгенерированная в такт
  2.  — бит, вычисленный в такт
  3. функция от переменных называется равновесной, если её вес Хэмминга равен
  4. [1] Архивная копия от 27 мая 2011 на Wayback Machine C. Berbain1, O. Billet1, A. Canteaut2, N. Courtois3, B. Debraize, H. Gilbert, L. Goubin, A. Gouget, L. Granboulan, C. Lauradoux, M. Minier, T. Pornin, H. Sibert Decim — a new stream cipher for hardware applications
  5. [2] Архивная копия от 27 мая 2011 на Wayback Machine Hongjun Wu, Bart Preneel Cryptanalysis of Stream Cipher DECIM Katholieke Universiteit Leuven, Dept. ESAT/COSIC