Decim

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

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

Введение

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

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

Начало работы потокового шифра Decim начинается с ввода 80-битного секретного ключа $K$ и 64-битного открытого ключа $IV$ (Initialization Vector). Затем, с помощью определённых линейных комбинаций битов $K$ и битов $IV$, использования нелинейной фильтрующей функции $F$ и применения механизма выборки ABSG вычисляется начальное состояние 192-битного РСЛОС. После выполнения всех этих операций начинается генерация ключевого потока $z=(z_t){|}_{t⩾0}$ и заполнение им специального буфера 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⩾0}$ последовательность битов, полученных с выхода РСЛОС, тогда правило вычисления бита на выходе РСЛОС имеет вид:

$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⩽j<k⩽7}{x}_{i_j}{x}_{i_k}$

Пусть

$y1=(y{1}_t){|}_{t⩾0}=F(s_{i_1+t},...,s_{i_7+t})$

$y2=(y{2}_t){|}_{t⩾0}=F(s_{i_8+t},...,s_{i_{14}+t})$

$𝐲=y{1}_0,y{2}_0,y{1}_1,y{2}_1,...$.

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

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

Тогда

$𝐲1_t=F(s_{t+1},s_{t+32},s_{t+40},s_{t+101},s_{t+164},s_{t+178},s_{t+187})$

$𝐲2_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 заключается в разбивке последовательности $𝐲=y{1}_0,y{2}_0,y{1}_1,y{2}_1,...$ на подпоследовательности вида $(b,b^i,\overline{b})$, где $b\in (0,1)$, и выдачи $b$, если $i=0$, и $\overline{b}$ в другом случае.

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

Input: ($y_0,y_1,y_2,\dots$)

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$==$\overline{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{array}{c}{K}_i\vee I{V}_{i}for0⩽i⩽56\\ K_{i-56}\vee \overline{I{V}_{i-56}}for56⩽i⩽111\\ K_{i-112}\oplus I{V}_{i-112}for112⩽i⩽191\end{array}$

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

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

РСЛОС

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

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

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

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

$F(x_{i_1},...,x_{i_7})=\sum _{1⩽j<k⩽7}{x}_{i_j}{x}_{i_k}$,

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

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

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

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

Ссылки

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