Decim

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

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

Введение

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

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

Начало работы потокового шифра Decim начинается с ввода 80-битного сектретного ключа $K$ и 64-битного открытого ключа $IV$ (Initialization Vector). Затем, с помощью определеннных линейных комбинаций битов $K$ и битов $IV$, использования нелинейной фильтрующей функции $F$ и применения механизма выборки ABSG вычисляется начальное состояние 192-битного РСЛОС. После выполнения всех этих операций начинается генерация ключевого потока $z=(z_t)|_{t\geqslant0}$^[1] и заполнение им специального буфера BUFFER, использующегося для обеспечения непрерывной выдачи битов $z_t$ на выход шифра, где происходит их сложение по модулю два с двоичной последовательностью символов открытого текста.

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

РСЛОС и фильтрующая функция $F$

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

$P(X)=X^{192}+X^{189}+X^{188}+X^{169}+X^{156}+X^{155}+X^{132}+X^{131}+X^{94}+X^{77}+X^{46}+X^{17}+X^{16}+X^5+1$

Обозначим через $s=(s_t)|_{t\geqslant0}$^[2] поcледовательность битов, полученных с выхода РСЛОС, тогда правило вычисления бита на выходе РСЛОС имеет вид:

$s_{192+n}=s_{187+n}\oplus s_{176+n}\oplus s_{175+n}\oplus s_{146+n}\oplus s_{115+n}\oplus s_{98+n}\oplus s_{61+n}\oplus s_{60+n}\oplus s_{37+n}\oplus s_{36+n}\oplus s_{23+n}\oplus s_{4+n}\oplus s_{3+n}\oplus s_{n}$

Для усложнений зависимостей между битами $s_t$ РСЛОС и битами $z_t$ используется нелинейная фильтрующая функция от семи переменных $F(x_1,...x_7)$. В каждый такт $F$ применяется дважды — к битам, стоящим на разных позициях в РСЛОС. Обозначим $F1(x_{i_1},...,x_{i_7})$ и $F2(x_{i_8},...x_{i_{14}})$ функции такие, что

$F1(x_{i_1},...,x_{i_7})=F(x_{i_1},...,x_{i_7})$

и

$F2(x_{i_8},...,x_{i_{14}})=F(x_{i_8},...,x_{i_{14}})$, где

$F(x_{i_1},...,x_{i_7})=\sum_{1\leqslant j<k\leqslant 7} {x_{i_j}x_{i_k}}$

Пусть

$y1=(y1_t)|_{t\geqslant0}=F(s_{i_1+t},...,s_{i_7+t})$

$y2=(y2_t)|_{t\geqslant0}=F(s_{i_8+t},...,s_{i_{14}+t})$

$\mathbf y=y1_0,y2_0,y1_1,y2_1,...$.

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

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

Тогда

$\mathbf y1_t=F(s_{t+1},s_{t+32},s_{t+40},s_{t+101},s_{t+164},s_{t+178},s_{t+187})$

$\mathbf y2_t=F(s_{t+6},s_{t+8},s_{t+60},s_{t+116},s_{t+145},s_{t+181},s_{t+191})$.

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

Механизм выборки ABSG используется для предотвращения алгебраических атак и некторых видов быстрых корреляционных атак с помощью десинхронизации фильтрованных битов РСЛОС $y_0,y_1,y_2,...$ и битов гамма $z_0,z_1,z_2,...$. Работа механизма выборки ABSG заключаестя в разбивке последовательности $\mathbf y=y1_0,y2_0,y1_1,y2_1,...$ на подпоследовательности вида $(b,b^i,\bar b)$, где $b \in{(0,1)}$, и выдачи $b$, если $i=0$, и $\bar b$ в другом случае.

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

Input: ($y_0,y_1,y_2,...$)

Set: $i=0$, $j=0$

Repeat the following steps:

1. $e=y_i$, $z_j = y_{i+1}$;
2. $i=i+1$;
3. while ($y_i$==$\bar e$) $i=i+1$;
4. $i=i+1$;
5. output $z_j$;
6. $j=j+1$;

Пример:

пусть $y=(0101001110100100011101)$, тогда, соответствующая последовательность на выходе ABSG имеет вид $z=(10111010)$.

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

Буфер BUFFER

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

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

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

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

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

$x_i={ \begin{cases} K_i \lor IV_i ~for ~0 \leqslant i \leqslant 56 \\ K_{i-56} \lor \bar {IV_{i-56}} ~for ~56 \leqslant i \leqslant 111\\ K_{i-112} \oplus IV_{i-112} ~for ~112 \leqslant i \leqslant 191\\ \end{cases}}$

Видно, что число всевозможных начальных состояний РСЛОС это $2^{56+56+24}$.

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

РСЛОС

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

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

Фильтрующая функция $F$

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

$F(x_{i_1},...,x_{i_7})=\sum_{1\leqslant j<k\leqslant 7} {x_{i_j}x_{i_k}}$,

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

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

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

Но, независимый криптоанализ, проведенный Хунян Ву и Бартом Пренилом, показал ненадежность шифра Decim, причем вычислительная сложность атаки оказалась не больше чем $O(2^{21})$, что является абсолютно неприемлемым^[5].

Примечания

1. ↑ $z_t$ — гамма, сгенерированная в такт $t$
2. ↑ $s_t$ — бит, вычисленный в такт $t$
3. ↑ функция от $n$ переменных называется равновесной, если её вес Хэмминга равен $2^{n-1}$
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

Литература

Габидулин Э. М., Кшевецкий А. С., Колыбельников А. И. Защита информации. — Москва: МФТИ, 2011. — 261 с. — ISBN 5-7417-0377-1.

Ссылки

• Aperiodic Propagation Criteria for Boolean Functions
• Finding Low Weight Polynomial Multiples Using Lattices
• Computing sparse multiples of polynomials