Decim

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

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

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

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

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 {\displaystyle 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 {\displaystyle s=(s_{t})|_{t\geqslant 0}} ^[2] последовательность битов, полученных с выхода РСЛОС, тогда правило вычисления бита на выходе РСЛОС имеет вид:

s 192 + n = s 187 + n ⊕ s 176 + n ⊕ s 175 + n ⊕ s 146 + n ⊕ s 115 + n ⊕ s 98 + n ⊕ s 61 + n ⊕ s 60 + n ⊕ s 37 + n ⊕ s 36 + n ⊕ s 23 + n ⊕ s 4 + n ⊕ s 3 + n ⊕ s n {\displaystyle 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 {\displaystyle s_{t}} РСЛОС и битами z t {\displaystyle z_{t}} используется нелинейная фильтрующая функция от семи переменных F ( x 1 , . . . x 7 ) {\displaystyle F(x_{1},...x_{7})} . В каждый такт F {\displaystyle F} применяется дважды — к битам, стоящим на разных позициях в РСЛОС. Обозначим F 1 ( x i 1 , . . . , x i 7 ) {\displaystyle F1(x_{i_{1}},...,x_{i_{7}})} и F 2 ( x i 8 , . . . x i 14 ) {\displaystyle F2(x_{i_{8}},...x_{i_{14}})} функции такие, что

F 1 ( x i 1 , . . . , x i 7 ) = F ( x i 1 , . . . , x i 7 ) {\displaystyle F1(x_{i_{1}},...,x_{i_{7}})=F(x_{i_{1}},...,x_{i_{7}})}

и

F 2 ( x i 8 , . . . , x i 14 ) = F ( x i 8 , . . . , x i 14 ) {\displaystyle F2(x_{i_{8}},...,x_{i_{14}})=F(x_{i_{8}},...,x_{i_{14}})} , где

F ( x i 1 , . . . , x i 7 ) = ∑ 1 ⩽ j < k ⩽ 7 x i j x i k {\displaystyle F(x_{i_{1}},...,x_{i_{7}})=\sum _{1\leqslant j<k\leqslant 7}{x_{i_{j}}x_{i_{k}}}}

Пусть

y 1 = ( y 1 t ) | t ⩾ 0 = F ( s i 1 + t , . . . , s i 7 + t ) {\displaystyle y1=(y1_{t})|_{t\geqslant 0}=F(s_{i_{1}+t},...,s_{i_{7}+t})}

y 2 = ( y 2 t ) | t ⩾ 0 = F ( s i 8 + t , . . . , s i 14 + t ) {\displaystyle y2=(y2_{t})|_{t\geqslant 0}=F(s_{i_{8}+t},...,s_{i_{14}+t})}

y = y 1 0 , y 2 0 , y 1 1 , y 2 1 , . . . {\displaystyle \mathbf {y} =y1_{0},y2_{0},y1_{1},y2_{1},...} .

Позиции битов РСЛОС, которые являются аргументами F 1 {\displaystyle F1} и F 2 {\displaystyle F2} :

• для F 1 {\displaystyle F1} : 1, 32, 40, 101, 164, 178, 187;
• для F 2 {\displaystyle F2} : 6, 8, 60, 116, 145, 181, 191.

Тогда

y 1 t = F ( s t + 1 , s t + 32 , s t + 40 , s t + 101 , s t + 164 , s t + 178 , s t + 187 ) {\displaystyle \mathbf {y} 1_{t}=F(s_{t+1},s_{t+32},s_{t+40},s_{t+101},s_{t+164},s_{t+178},s_{t+187})}

y 2 t = F ( s t + 6 , s t + 8 , s t + 60 , s t + 116 , s t + 145 , s t + 181 , s t + 191 ) {\displaystyle \mathbf {y} 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 используется для предотвращения алгебраических атак и некоторых видов быстрых корреляционных атак с помощью десинхронизации фильтрованных битов РСЛОС y 0 , y 1 , y 2 , . . . {\displaystyle y_{0},y_{1},y_{2},...} и битов гамма z 0 , z 1 , z 2 , . . . {\displaystyle z_{0},z_{1},z_{2},...} . Работа механизма выборки ABSG заключается в разбивке последовательности y = y 1 0 , y 2 0 , y 1 1 , y 2 1 , . . . {\displaystyle \mathbf {y} =y1_{0},y2_{0},y1_{1},y2_{1},...} на подпоследовательности вида ( b , b i , b ¯ ) {\displaystyle (b,b^{i},{\bar {b}})} , где b ∈ ( 0 , 1 ) {\displaystyle b\in {(0,1)}} , и выдачи b {\displaystyle b} , если i = 0 {\displaystyle i=0} , и b ¯ {\displaystyle {\bar {b}}} в другом случае.

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

Input: ( y 0 , y 1 , y 2 , … {\displaystyle y_{0},y_{1},y_{2},\dots } )

Set: i = 0 {\displaystyle i=0} , j = 0 {\displaystyle j=0}

Repeat the following steps:

1. e = y i {\displaystyle e=y_{i}} , z j = y i + 1 {\displaystyle z_{j}=y_{i+1}} ;
2. i = i + 1 {\displaystyle i=i+1} ;
3. while ( y i {\displaystyle y_{i}} == e ¯ {\displaystyle {\bar {e}}} ) i = i + 1 {\displaystyle i=i+1} ;
4. i = i + 1 {\displaystyle i=i+1} ;
5. output z j {\displaystyle z_{j}} ;
6. j = j + 1 {\displaystyle j=j+1} ;

Пример:

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

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

Так как выдача битов механизмом ABSG непостоянна (для генерации одного бита z t {\displaystyle z_{t}} используется, в среднем, три бита y t {\displaystyle y_{t}} ), а во время работы потокового шифра на каждый такт должен выдаваться бит гамма, то для непрерывной выдачи битов гамма используется буфер BUFFER.

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

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

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

x i = { K i ∨ I V i   f o r   0 ⩽ i ⩽ 56 K i − 56 ∨ I V i − 56 ¯   f o r   56 ⩽ i ⩽ 111 K i − 112 ⊕ I V i − 112   f o r   112 ⩽ i ⩽ 191 {\displaystyle 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 {\displaystyle 2^{56+56+24}} .

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

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

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

F ( x i 1 , . . . , x i 7 ) = ∑ 1 ⩽ j < k ⩽ 7 x i j x i k {\displaystyle F(x_{i_{1}},...,x_{i_{7}})=\sum _{1\leqslant j<k\leqslant 7}{x_{i_{j}}x_{i_{k}}}} ,

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

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

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

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