Decim

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

Введение

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

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

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

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

РСЛОС и фильтрующая функция <math>F</math>

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

<math>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</math>

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

<math>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}</math>

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

<math>F1(x_{i_1},...,x_{i_7})=F(x_{i_1},...,x_{i_7})</math>

и

<math>F2(x_{i_8},...,x_{i_{14}})=F(x_{i_8},...,x_{i_{14}})</math>, где

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

Пусть

<math>y1=(y1_t)|_{t\geqslant0}=F(s_{i_1+t},...,s_{i_7+t})</math>

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

<math>\mathbf y=y1_0,y2_0,y1_1,y2_1,...</math>.

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

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

Тогда

<math>\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})</math>

<math>\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})</math>.

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

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

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

Input: (<math>y_0,y_1,y_2,\dots</math>)

Set: <math>i=0</math>, <math>j=0</math>

Repeat the following steps:

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

Пример:

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

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

Буфер BUFFER

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

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

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

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

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

<math>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}} </math>

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

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

РСЛОС

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

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

Фильтрующая функция <math>F</math>

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

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

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

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

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

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

Ссылки

• [www.ii.uib.no/~matthew/GenDiff4.pdf Aperiodic Propagation Criteria for Boolean Functions]
• [www.cs.uwaterloo.ca/~droche/papers/spmul.pdf Finding Low Weight Polynomial Multiples Using Lattices]
• [arxiv.org/PS_cache/arxiv/pdf/1009/1009.3214v2.pdf Computing sparse multiples of polynomials]

Отрывок, характеризующий Decim

В начале 1806 года Николай Ростов вернулся в отпуск. Денисов ехал тоже домой в Воронеж, и Ростов уговорил его ехать с собой до Москвы и остановиться у них в доме. На предпоследней станции, встретив товарища, Денисов выпил с ним три бутылки вина и подъезжая к Москве, несмотря на ухабы дороги, не просыпался, лежа на дне перекладных саней, подле Ростова, который, по мере приближения к Москве, приходил все более и более в нетерпение.
«Скоро ли? Скоро ли? О, эти несносные улицы, лавки, калачи, фонари, извозчики!» думал Ростов, когда уже они записали свои отпуски на заставе и въехали в Москву.
– Денисов, приехали! Спит! – говорил он, всем телом подаваясь вперед, как будто он этим положением надеялся ускорить движение саней. Денисов не откликался.
– Вот он угол перекресток, где Захар извозчик стоит; вот он и Захар, и всё та же лошадь. Вот и лавочка, где пряники покупали. Скоро ли? Ну!
– К какому дому то? – спросил ямщик.
– Да вон на конце, к большому, как ты не видишь! Это наш дом, – говорил Ростов, – ведь это наш дом! Денисов! Денисов! Сейчас приедем.
Денисов поднял голову, откашлялся и ничего не ответил.
– Дмитрий, – обратился Ростов к лакею на облучке. – Ведь это у нас огонь?
– Так точно с и у папеньки в кабинете светится.
– Еще не ложились? А? как ты думаешь? Смотри же не забудь, тотчас достань мне новую венгерку, – прибавил Ростов, ощупывая новые усы. – Ну же пошел, – кричал он ямщику. – Да проснись же, Вася, – обращался он к Денисову, который опять опустил голову. – Да ну же, пошел, три целковых на водку, пошел! – закричал Ростов, когда уже сани были за три дома от подъезда. Ему казалось, что лошади не двигаются. Наконец сани взяли вправо к подъезду; над головой своей Ростов увидал знакомый карниз с отбитой штукатуркой, крыльцо, тротуарный столб. Он на ходу выскочил из саней и побежал в сени. Дом также стоял неподвижно, нерадушно, как будто ему дела не было до того, кто приехал в него. В сенях никого не было. «Боже мой! все ли благополучно?» подумал Ростов, с замиранием сердца останавливаясь на минуту и тотчас пускаясь бежать дальше по сеням и знакомым, покривившимся ступеням. Всё та же дверная ручка замка, за нечистоту которой сердилась графиня, также слабо отворялась. В передней горела одна сальная свеча.
Старик Михайла спал на ларе. Прокофий, выездной лакей, тот, который был так силен, что за задок поднимал карету, сидел и вязал из покромок лапти. Он взглянул на отворившуюся дверь, и равнодушное, сонное выражение его вдруг преобразилось в восторженно испуганное.
– Батюшки, светы! Граф молодой! – вскрикнул он, узнав молодого барина. – Что ж это? Голубчик мой! – И Прокофий, трясясь от волненья, бросился к двери в гостиную, вероятно для того, чтобы объявить, но видно опять раздумал, вернулся назад и припал к плечу молодого барина.
– Здоровы? – спросил Ростов, выдергивая у него свою руку.
– Слава Богу! Всё слава Богу! сейчас только покушали! Дай на себя посмотреть, ваше сиятельство!
– Всё совсем благополучно?
– Слава Богу, слава Богу!
Ростов, забыв совершенно о Денисове, не желая никому дать предупредить себя, скинул шубу и на цыпочках побежал в темную, большую залу. Всё то же, те же ломберные столы, та же люстра в чехле; но кто то уж видел молодого барина, и не успел он добежать до гостиной, как что то стремительно, как буря, вылетело из боковой двери и обняло и стало целовать его. Еще другое, третье такое же существо выскочило из другой, третьей двери; еще объятия, еще поцелуи, еще крики, слезы радости. Он не мог разобрать, где и кто папа, кто Наташа, кто Петя. Все кричали, говорили и целовали его в одно и то же время. Только матери не было в числе их – это он помнил.
– А я то, не знал… Николушка… друг мой!
– Вот он… наш то… Друг мой, Коля… Переменился! Нет свечей! Чаю!
– Да меня то поцелуй!
– Душенька… а меня то.
Соня, Наташа, Петя, Анна Михайловна, Вера, старый граф, обнимали его; и люди и горничные, наполнив комнаты, приговаривали и ахали.
Петя повис на его ногах. – А меня то! – кричал он. Наташа, после того, как она, пригнув его к себе, расцеловала всё его лицо, отскочила от него и держась за полу его венгерки, прыгала как коза всё на одном месте и пронзительно визжала.
Со всех сторон были блестящие слезами радости, любящие глаза, со всех сторон были губы, искавшие поцелуя.
Соня красная, как кумач, тоже держалась за его руку и вся сияла в блаженном взгляде, устремленном в его глаза, которых она ждала. Соне минуло уже 16 лет, и она была очень красива, особенно в эту минуту счастливого, восторженного оживления. Она смотрела на него, не спуская глаз, улыбаясь и задерживая дыхание. Он благодарно взглянул на нее; но всё еще ждал и искал кого то. Старая графиня еще не выходила. И вот послышались шаги в дверях. Шаги такие быстрые, что это не могли быть шаги его матери.
Но это была она в новом, незнакомом еще ему, сшитом без него платье. Все оставили его, и он побежал к ней. Когда они сошлись, она упала на его грудь рыдая. Она не могла поднять лица и только прижимала его к холодным снуркам его венгерки. Денисов, никем не замеченный, войдя в комнату, стоял тут же и, глядя на них, тер себе глаза.
– Василий Денисов, друг вашего сына, – сказал он, рекомендуясь графу, вопросительно смотревшему на него.
– Милости прошу. Знаю, знаю, – сказал граф, целуя и обнимая Денисова. – Николушка писал… Наташа, Вера, вот он Денисов.
Те же счастливые, восторженные лица обратились на мохнатую фигуру Денисова и окружили его.
– Голубчик, Денисов! – визгнула Наташа, не помнившая себя от восторга, подскочила к нему, обняла и поцеловала его. Все смутились поступком Наташи. Денисов тоже покраснел, но улыбнулся и взяв руку Наташи, поцеловал ее.
Денисова отвели в приготовленную для него комнату, а Ростовы все собрались в диванную около Николушки.
Старая графиня, не выпуская его руки, которую она всякую минуту целовала, сидела с ним рядом; остальные, столпившись вокруг них, ловили каждое его движенье, слово, взгляд, и не спускали с него восторженно влюбленных глаз. Брат и сестры спорили и перехватывали места друг у друга поближе к нему, и дрались за то, кому принести ему чай, платок, трубку.
Ростов был очень счастлив любовью, которую ему выказывали; но первая минута его встречи была так блаженна, что теперешнего его счастия ему казалось мало, и он всё ждал чего то еще, и еще, и еще.
На другое утро приезжие спали с дороги до 10 го часа.
В предшествующей комнате валялись сабли, сумки, ташки, раскрытые чемоданы, грязные сапоги. Вычищенные две пары со шпорами были только что поставлены у стенки. Слуги приносили умывальники, горячую воду для бритья и вычищенные платья. Пахло табаком и мужчинами.
– Гей, Г'ишка, т'убку! – крикнул хриплый голос Васьки Денисова. – Ростов, вставай!
Ростов, протирая слипавшиеся глаза, поднял спутанную голову с жаркой подушки.
– А что поздно? – Поздно, 10 й час, – отвечал Наташин голос, и в соседней комнате послышалось шуршанье крахмаленных платьев, шопот и смех девичьих голосов, и в чуть растворенную дверь мелькнуло что то голубое, ленты, черные волоса и веселые лица. Это была Наташа с Соней и Петей, которые пришли наведаться, не встал ли.
– Николенька, вставай! – опять послышался голос Наташи у двери.
– Сейчас!
В это время Петя, в первой комнате, увидав и схватив сабли, и испытывая тот восторг, который испытывают мальчики, при виде воинственного старшего брата, и забыв, что сестрам неприлично видеть раздетых мужчин, отворил дверь.
– Это твоя сабля? – кричал он. Девочки отскочили. Денисов с испуганными глазами спрятал свои мохнатые ноги в одеяло, оглядываясь за помощью на товарища. Дверь пропустила Петю и опять затворилась. За дверью послышался смех.
– Николенька, выходи в халате, – проговорил голос Наташи.
– Это твоя сабля? – спросил Петя, – или это ваша? – с подобострастным уважением обратился он к усатому, черному Денисову.
Ростов поспешно обулся, надел халат и вышел. Наташа надела один сапог с шпорой и влезала в другой. Соня кружилась и только что хотела раздуть платье и присесть, когда он вышел. Обе были в одинаковых, новеньких, голубых платьях – свежие, румяные, веселые. Соня убежала, а Наташа, взяв брата под руку, повела его в диванную, и у них начался разговор. Они не успевали спрашивать друг друга и отвечать на вопросы о тысячах мелочей, которые могли интересовать только их одних. Наташа смеялась при всяком слове, которое он говорил и которое она говорила, не потому, чтобы было смешно то, что они говорили, но потому, что ей было весело и она не в силах была удерживать своей радости, выражавшейся смехом.
– Ах, как хорошо, отлично! – приговаривала она ко всему. Ростов почувствовал, как под влиянием жарких лучей любви, в первый раз через полтора года, на душе его и на лице распускалась та детская улыбка, которою он ни разу не улыбался с тех пор, как выехал из дома.
– Нет, послушай, – сказала она, – ты теперь совсем мужчина? Я ужасно рада, что ты мой брат. – Она тронула его усы. – Мне хочется знать, какие вы мужчины? Такие ли, как мы? Нет?
– Отчего Соня убежала? – спрашивал Ростов.
– Да. Это еще целая история! Как ты будешь говорить с Соней? Ты или вы?
– Как случится, – сказал Ростов.
– Говори ей вы, пожалуйста, я тебе после скажу.
– Да что же?
– Ну я теперь скажу. Ты знаешь, что Соня мой друг, такой друг, что я руку сожгу для нее. Вот посмотри. – Она засучила свой кисейный рукав и показала на своей длинной, худой и нежной ручке под плечом, гораздо выше локтя (в том месте, которое закрыто бывает и бальными платьями) красную метину.