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, соответствует бит на выходе, что и видно из примера.

Буфер BUFFER[править | править вики-текст]

Так как выдача битов механизмом 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] 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] Hongjun Wu, Bart Preneel Cryptanalysis of Stream Cipher DECIM Katholieke Universiteit Leuven, Dept. ESAT/COSIC

Ссылки[править | править вики-текст]