Потоковый шифр

Определение:

Синхронные потоковые шифры (СПШ) — шифры, в которых поток ключей генерируется независимо от открытого текста и шифротекста.

При шифровании генератор потока ключей выдаёт биты потока ключей, которые идентичны битам потока ключей при дешифровании. Потеря знака шифротекста приведёт к нарушению синхронизации между этими двумя генераторами и невозможности расшифрования оставшейся части сообщения. Очевидно, что в этой ситуации отправитель и получатель должны повторно синхронизоваться для продолжения работы.

Обычно синхронизация производится вставкой в передаваемое сообщение специальных маркеров. В результате этого пропущенный при передаче знак приводит к неверному расшифрованию лишь до тех пор, пока не будет принят один из маркеров.

Заметим, что выполняться синхронизация должна так, чтобы ни одна часть потока ключей не была повторена. Поэтому переводить генератор в более раннее состояние не имеет смысла.

Плюсы СПШ:

• отсутствие эффекта распространения ошибок (только искажённый бит будет расшифрован неверно);
• предохраняют от любых вставок и удалений шифротекста, так как они приведут к потере синхронизации и будут обнаружены.

Минусы СПШ:

• уязвимы для изменения отдельных бит шифрованного текста. Если злоумышленнику известен открытый текст, он может изменить эти биты так, чтобы они расшифровывались, как ему надо.

Основная идея построения была запатентована в 1946 г. в США.

Определение:

Самосинхронизирующиеся потоковые шифры (асинхронные потоковые шифры (АПШ)) — шифры, в которых ключевой поток создаётся функцией ключа и фиксированного числа знаков шифротекста.

Итак, внутреннее состояние генератора потока ключей является функцией предыдущих N битов шифротекста. Поэтому расшифрующий генератор потока ключей, приняв N битов, автоматически синхронизируется с шифрующим генератором.

Реализация этого режима происходит следующим образом: каждое сообщение начинается случайным заголовком длиной N битов; заголовок шифруется, передаётся и расшифровывается; расшифровка является неправильной, зато после этих N бит оба генератора будут синхронизированы.

Плюсы АПШ:

• Размешивание статистики открытого текста. Так как каждый знак открытого текста влияет на следующий шифротекст, статистические свойства открытого текста распространяются на весь шифротекст. Следовательно, АПШ может быть более устойчивым к атакам на основе избыточности открытого текста, чем СПШ.

Минусы АПШ:

• распространение ошибки (каждому неправильному биту шифротекста соответствуют N ошибок в открытом тексте);
• чувствительны к вскрытию повторной передачей.

Есть несколько причин использования линейных регистров сдвига в криптографии:

• высокое быстродействие криптографических алгоритмов
• применение только простейших операций сложения и умножения, аппаратно реализованных практически во всех вычислительных устройствах
• хорошие криптографические свойства (генерируемые последовательности имеют большой период и хорошие статистические свойства)
• легкость анализа с использованием алгебраических методов за счет линейной структуры

Определение: Регистр сдвига с линейной обратной связью длины L состоит из L ячеек пронумерованных ${\displaystyle 0,1,2,\dots L-1}$,каждая из которых способна хранить 1 бит и имеет один вход и один выход; и синхросигнала (clock), который контролирует смещение данных. В течение каждой единицы времени выполняются следующие операции:

• содержимое ячейки ${\displaystyle L-1}$ формирует часть выходной последовательности;
• содержимое ${\displaystyle i}$-той ячейки перемещается в ячейку ${\displaystyle i+1}$ для любого ${\displaystyle i}$, ${\displaystyle 0\leq i<L-1}$.
• новое содержимое ячейки ${\displaystyle 0}$ определяется битом обратной связи, который вычисляется сложением по модулю 2 с определёнными коэффициентами битов ячеек ${\displaystyle 0,1,2,\dots L-1}$.

Регистр сдвига с линейной обратной связью.

На первом шаге: ${\displaystyle S_{L}=c_{1}\cdot S_{L-1}\oplus c_{2}\cdot S_{L-2}\oplus \dots \oplus c_{L}\cdot S_{0}.}$

На втором шаге: ${\displaystyle S_{L+1}=c_{1}\cdot S_{L}\oplus c_{2}\cdot S_{L-1}\oplus \dots \oplus c_{L}\cdot S_{1}.}$

Следующее соотношение описывает в общем виде работу РСЛОС:

${\displaystyle S_{j}=c_{1}\cdot S_{j-1}\oplus c_{2}\cdot S_{j-2}\oplus \dots \oplus c_{L}\cdot S_{j-L}.}$
Если мы запишем во все ячейки биты равны нулю, то система будет генерировать последовательность, состоящую из всех нулей. Если записать ненулевые биты, то получим полубесконечную последовательность. Последовательность определяется коэффициентами ${\displaystyle c_{1},c_{2},\dots ,c_{L}.}$
Посмотрим, каким может быть период ${\displaystyle T}$ такой системы:
Число ненулевых заполнений:${\displaystyle 2^{L}-1.}$ Значит, ${\displaystyle T\leqslant 2^{L}-1}$.
После возникновения одного заполнения, которое было раньше, процесс начнёт повторяться. Процесс заполнения регистра, как показано выше, представим линейным разностным уравнением. Перенесём все члены в одну часть равенства, получим:
${\displaystyle S_{j}\oplus c_{1}\cdot S_{j-1}\oplus c_{2}\cdot S_{j-2}\oplus \dots \oplus c_{L}\cdot S_{j-L}=0}$.

Обозначим: ${\displaystyle S_{j}=D^{-j}}$. Тогда:
${\displaystyle (1\oplus c_{1}\cdot D\oplus c_{2}\cdot D^{2}\oplus \dots \oplus c_{L}\cdot D^{L})\cdot D^{-j}.}$

${\displaystyle C(D)=1\oplus c_{1}\cdot D\oplus c_{2}\cdot D^{2}\oplus \dots \oplus c_{L}\cdot D^{L}.}$

Важным свойством этого многочлена является - приводимость.
Определение:
Многочлен называется приводимым, если он может быть представлен как произведение двух многочленов меньших степеней с коэффициентами из данного поля (в нашем случае с двоичными коэффициентами). Если такое представление не имеет место, то многочлен называется неприводимым.
Если многочлен ${\displaystyle C(D)}$ является неприводимым и примитивным, то период будет совпадать с максимально возможным периодом, равным ${\displaystyle 2^{L}-1.}$

Пример.

Пример: Возьмём неприводимый примитивный многочлен ${\displaystyle C(D)=D^{3}+D^{2}+1(c_{3}=1,c_{2}=1,c_{1}=0).}$ Этот многочлен можно записать, как ${\displaystyle (3,2,0)}$ – выписаны степени, при которых стоят ненулевые коэффициенты.
Запишем в исходном состоянии в ячейки ${\displaystyle 001}$ и определим длину периода генератора:

Период генератора равен ${\displaystyle 7(2^{3}-1=7).}$ На выходе генератора буде последовательность: ${\displaystyle 100101110010111001011\dots }$
Приведём примеры некоторых примитивных многочленов по модулю 2:

${\displaystyle (1,0),(2,1,0),(3,1,0),(4,1,0),(5,2,0),(6,1,0),(7,1,0),(7,3,0),(8,4,3,2,0),(9,4,0)\dots }$

Линейная сложность бинарной последовательности – одна из самых важных характеристик работы РСЛОС. Поэтому остановимся на этой теме поподробнее.
Прежде чем дать определение линейной сложности введём некоторые обозначения.
${\displaystyle S}$ - бесконечная последовательность с членами ${\displaystyle S1,S2,S3,\dots }$
${\displaystyle S_{n}}$ – конечная последовательность длины ${\displaystyle n}$, членами которой являются ${\displaystyle S_{1},S_{2},S_{3},\dots ,S_{n-1}.}$
Говорят, что РСЛОС генерирует последовательность ${\displaystyle S}$, если существует некоторое исходное состояние, при котором выходная последовательность РСЛОС совпадает с ${\displaystyle S}$. Аналогично, говорят, что РСЛОС генерирует конечную последовательность ${\displaystyle S_{n}}$, если существует некоторое начальное состояние, для которого выходная последовательность РСЛОС имеет в качестве первых ${\displaystyle n}$ членов члены последовательности ${\displaystyle S_{n}}$.
Наконец дадим определение линейной сложности бесконечной двоичной последовательности.
Определение: Линейной сложностью бесконечной двоичной последовательности ${\displaystyle S}$ называется число ${\displaystyle L(S)}$, которое определяется следующим образом:

• Если ${\displaystyle S}$ – нулевая последовательность ${\displaystyle S=0,0,0,0,\dots ,}$, то ${\displaystyle L(S)=0.}$
• Если не существует РСЛОС, который генерирует ${\displaystyle S}$, то ${\displaystyle L(S)}$ равно бесконечности.
• Иначе, ${\displaystyle L(S)}$ есть длина самого короткого РСЛОС, который генерирует ${\displaystyle S}$.

Определение:
Линейной сложностью конечной двоичной последовательности ${\displaystyle S_{n}}$ называется число ${\displaystyle L(S_{n})}$, которое равно длине самого короткого РСЛОС, который генерирует последовательность, имеющую в качестве первых ${\displaystyle n}$ членов ${\displaystyle S_{n}}$.
Свойства линейной сложности: Пусть ${\displaystyle S}$ и ${\displaystyle K}$ – двоичные последовательности. Тогда:
1. Для любого ${\displaystyle n>0}$ линейная сложность подпоследовательности ${\displaystyle S_{n}}$ удовлетворяет неравенствам ${\displaystyle 0\leqslant L(S_{n})\leqslant n.}$
2. ${\displaystyle L(S_{n})=0}$ тогда и только тогда, когда ${\displaystyle S_{n}}$ – нулевая последовательность длины ${\displaystyle n}$.
3. ${\displaystyle L(S_{n})=n}$ тогда и только тогда, когда ${\displaystyle S_{n}=0,0,0,\dots ,1}$.
4. Если ${\displaystyle S}$ – периодическая с периодом ${\displaystyle N}$, тогда ${\displaystyle L(S_{n})\leqslant N.}$
5. ${\displaystyle L(S\oplus K)\leqslant L(S)+L(K).}$
Эффективным алгоритмом определения линейной сложности конечной двоичной последовательности является алгоритм Берлекемпа-Месси.

Нелинейная комбинация генераторов

Известно, что каждая Булева функция ${\displaystyle f(x_{1},x_{2},\dots ,x_{n})}$ может быть записана как сумма по модулю 2 произведений порядков ${\displaystyle m}$ независимых переменных, ${\displaystyle 0\leqslant m\leqslant n}$. Это выражение называется алгебраической нормальной формой функции ${\displaystyle f}$. Нелинейным порядком функции ${\displaystyle f}$ называется максимальный порядок членов в записи её алгебраической нормальной формы.
Например, Булева функция ${\displaystyle f(x_{1},x_{2},x_{3},x_{4})=x_{1}\oplus x_{2}\oplus x_{4}\oplus x_{1}x_{3}\oplus x_{2}x_{3}x_{4}}$ имеет нелинейный порядок 3. Максимально возможный нелинейный порядок Булевой функции равен количеству переменных ${\displaystyle n.}$
Предположим теперь, что у нас ${\displaystyle n}$ регистров сдвига с линейной обратной связью, их длины ${\displaystyle L_{1},L_{2},L_{3},\dots ,L_{n}}$ попарно различны и больше двух. Все регистры объединены нелинейной функцией ${\displaystyle f(x_{1},x_{2},\dots ,x_{n})}$, как показано на рисунке. Функция ${\displaystyle f}$ представлена в алгебраической нормальной форме. Тогда линейная сложность потока ключей равна ${\displaystyle f(L_{1},L_{2},\dots ,L_{n})}$.
Если ${\displaystyle L_{1},L_{2},\dots ,L_{n}}$ – попарно взаимно-простые числа, то длина периода ключевого потока равна: ${\displaystyle (2^{L_{1}}-1)\cdot (2^{L_{2}}-1)\cdots (2^{L_{n}}-1)}$. Например, если ${\displaystyle L_{i}=10}$, то ${\displaystyle (2^{L_{1}}-1)\approx 10^{3}}$. И длина периода ключевого потока равна ${\displaystyle (10^{3})^{n}}$.

Генератор Геффа

Пример (генератор Геффа):
В этом генераторе используются три РСЛОС, объединённые нелинейным образом. Длины этих регистров ${\displaystyle L_{1},L_{2},L_{3}}$ попарно простые числа.
Нелинейную функцию для данного генератора можно записать следующим образом:

${\displaystyle f(x_{1},x_{2},x_{3})=x_{1}x_{2}\oplus (1+x_{2})x_{3}=x_{1}x_{2}\oplus x_{2}x_{3}\oplus x_{3}.}$

Длина периода: ${\displaystyle (2^{L_{1}}-1)\cdot (2^{L_{2}}-1)\cdot (2^{L_{3}}-1).}$

Линейная сложность: ${\displaystyle L=L_{1}\cdot L_{2}+L_{2}\cdot L_{3}+L_{3}.}$

Генератор Геффа криптографически слаб, потому что информация о состояниях генераторов РСЛОС 1 и РСЛОС 3 содержится в его выходной последовательности. Для того чтобы понять это, обозначим ${\displaystyle x_{1}(t),x_{2}(t),x_{3}(t),z(t)}$ ${\displaystyle t}$-е выходные биты РСЛОС 1,2,3 и потока ключей, соответственно. Тогда корреляционная вероятность последовательности ${\displaystyle x_{1}(t)}$ по отношению к последовательности ${\displaystyle z(t)}$:

${\displaystyle P(z(t)=x_{1}(t))=P(x_{2}(t)=1)+P(x_{2}(t)=0)\cdot P(x_{3}(t)=x_{1}(t))=1/2+1/2\cdot 1/2=3/4.}$

Аналогично, ${\displaystyle P(z(t)=x_{3}(t))=3/4.}$
По этой причине, несмотря на длинный период и достаточно высокую линейную сложность, генератор Геффа поддаётся корреляционным атакам.

Генератор на нелинейном фильтре

Выход каждой ячейки подаётся на вход некоторой нелинейной булевой фильтрующей функции ${\displaystyle f}$. Предположим, что фильтрующая функция порядка ${\displaystyle m}$, тогда линейная сложность потока ключей не больше ${\displaystyle L_{m}=\sum _{i=1}^{m}{L \choose i}}$.

В нелинейных комбинациях генераторов и генераторах на нелинейных фильтрах перемещение данных во всех РСЛОС контролируется одним синхросигналом.
Основная идея функционирования рассматриваемого типа генераторов — внести нелинейность в работу генераторов потока ключей, основанных на РСЛОС, путём управления синхросигналом одного регистра выходной последовательностью другого.
Есть 2 типа генераторов, основанных на управлении синхросигналом:
1. генератор переменного шага
2. сжимающий генератор.

Основная идея:
РСЛОС 1 используется для управления передвижением битов двух других РСЛОС 2 и 3.

Генератор переменного шага

Алгоритм работы:
1. Регистр РСЛОС 1 синхронизован внешним синхросигналом
2. Если на выходе регистра РСЛОС 1 единица, то на регистр РСЛОС 2 подаётся синхросигнал, а РСЛОС 3 повторяет свой предыдущий выходной бит (для начального момента времени предыдущий выходной бит РСЛОС 3 принимается равным 0)
3. Если на выходе регистра РСЛОС 1 ноль, то на регистр РСЛОС 3 подаётся синхросигнал, а РСЛОС 2 повторяет свой предыдущий выходной бит (для начального момента времени предыдущий выходной бит РСЛОС 2 также принимается равным 0)
4. Выходная последовательность битов генератора с переменным шагом является результатом применения операции побитового исключающего ИЛИ к выходным последовательностям регистров РСЛОС 2 и РСЛОС 3.

Увеличение безопасности генераторов с переменным шагом:

• длины регистров РСЛОС 1, РСЛОС 2, РСЛОС 3 должны быть выбраны попарно простыми числами
• длины этих регистров должны быть близкими числами.

Сжимающий генератор

Контролирующий регистр РСЛОС 1 используется для управления выходом РСЛОС 2. Алгоритм:

1. Регистры РСЛОС 1 и РСЛОС 2 синхронизованы общим синхросигналом;
2. Если выходной бит РСЛОС 1 равен 1, выход генератора формируется выходным битом регистра РСЛОС 2;
3. Если выходной бит РСЛОС 1 равен 0, выходной бит регистра РСЛОС 2 отбрасывается.

Сжимающий генератор прост, масштабируем и имеет хорошие защитные свойства. Его недостаток состоит в том, что скорость генерации ключа не будет постоянной, если не принять некоторых предосторожностей.

Для увеличения безопасности сжимающего генератора:

• длины регистров РСЛОС 1 и РСЛОС 2 должны быть взаимно простыми числами;
• желательно использовать скрытое соединение между регистрами РСЛОС 1 и РСЛОС 2.

К этому классу относятся атаки, осуществляющие полный перебор всех возможных вариантов. Сложность полного перебора зависит от количества всех возможных решений задачи (в частности, размера пространства ключей или пространства открытых текстов). Этот класс атак применим ко всем видам систем поточного шифрования. При разработке систем шифрования разработчики стремятся сделать так, чтобы этот вид атак был наиболее эффективным по сравнению с другими существующими методами взлома.

Статистические атаки делятся на два подкласса:

• метод криптоанализа статистических свойств шифрующей гаммы: направлен на изучение выходной последовательности криптосистемы; криптоаналитик пытается установить значение следующего бита последовательности с вероятностью выше вероятности случайного выбора с помощью различных статистических тестов.
• метод криптоанализа сложности последовательности: криптоаналитик пытается найти способ генерировать последовательность, аналогичную гамме, но более просто реализуемым способом.

Оба метода используют принцип линейной сложности.

Этот вид атак рассматривается в предположении, что криптоаналитику известны описание генератора, открытый и соответствующий закрытый тексты. Задача криптоаналитика определить использованный ключ (начальное заполнение регистров). Виды аналитических атак, применяемые к синхронным поточным шифрам:

• корреляционные
• компромисс “время-память”
• инверсионная
• “предполагай и определяй”
• на ключевую загрузку и реинициализацию
• XSL-атака

Являются наиболее распространёнными атаками для взлома поточных шифров.

Известно, что работа по вскрытию криптосистемы может быть значительно сокращена, если нелинейная функция пропускает на выход информацию о внутренних компонентах генератора. Поэтому для восстановления начального заполнения регистров корреляционные атаки исследуют корреляцию выходной последовательности шифросистемы с выходной последовательностью регистров.

Существуют следующие подклассы корреляционных атак:

• Базовые корреляционные атаки
• Атаки, основанные на низко-весовых проверках четности
• Атаки, основанные на использовании сверточных кодов
• Атаки, использующие технику турбо кодов
• Атаки, основанные на восстановлении линейных полиномов
• Быстрые корреляционные атаки.

Базовые корреляционные атаки

Схема базовой корреляционной атаки

Рассмотрим на примере базовой корреляционной атаки Зигенталера («разделяй и вскрывай»), которая основана на понятии расстояния Хэмминга между двумя двоичными последовательностями одинаковой длины. Применима к комбинирующим генераторам.

Для выявления влияния j-го линейного регистра сдвига (с выходной последовательностью {x^(j)} на гамму шифра {g} моделируется часть генератора как двоичный симметричный канал (ДСК). Алгоритм атаки состоит из двух этапов (иногда называемые фазами):

1. вычисления корреляционной вероятности ${\displaystyle p_{j}=P(g={x^{(j)}})}$ исходя из комбинирующей функции ${\displaystyle f}$ и второго этапа.
2. перебор начальных заполнений регистра. На этом этапе определяется наличие корреляции данного фрагмента гаммы ${\displaystyle g}$ с соответствующим фрагментом из ${\displaystyle x_{d}^{(j)}}$, путём вычисления функции кросс-корреляции ${\displaystyle C_{x^{j},{g}}(d)={\frac {1}{n}}\cdot \sum _{i=1}^{n}(-1)^{g_{i}}\cdot (-1)^{x_{i+d}^{(j)}}}$ и сравнения этого значения с некоторым числом ${\displaystyle T}$.

В случае успеха при сравнении, фаза называется верной и происходит переход к следующему регистру ${\displaystyle j+1}$. Иначе, фаза называется неверной и переходят к ${\displaystyle d=d+1,d=1,2,\dots ,2^{L_{j}}}$. Выходными значениями этого алгоритма являются состояния ${\displaystyle {x_{0}^{j}}}$, вносящие информацию в гамму.

Теперь немного о подборе порогового значения ${\displaystyle T}$ и необходимого для успешного криптоанализа количество бит гаммы ${\displaystyle n}$: Задаём нужные нам вероятности «ложной тревоги» ${\displaystyle P_{f}=P(C_{x^{j},{g}}(d)\geq T|WrongPhase)}$ и пропуска истинного начального заполнения ${\displaystyle P_{m}=P(C_{x^{j},{g}}(d)<T|RightPhase)}$ .

Например, выбрали ${\displaystyle P_{m}=0.01,P_{f}=2^{-L}}$, где ${\displaystyle L}$ - длина регистра. А затем из этих условий находим ${\displaystyle T}$ и ${\displaystyle n}$.

Атаки, основанные на низко-весовых проверках четности

Примером этого подкласса атак может служить быстрая корреляционная атака Майера и Штаффельбаха. Применима она как к фильтр-генераторам, так и комбинирующим генераторам и является базовой для всех остальных быстрых корреляционных атак данного типа. Идея атаки основывается на использовании уравнений проверки четности для полинома обратной связи линейного регистра.

Быстрые корреляционные атаки

Под быстрыми корреляционными атаками подразумеваются атаки, вычислительная сложность которых значительно меньше вычислительной сложности силовых атак.
Этот вид атак сводит проблему декодирования в двоичном симметричном канале к проблеме криптоанализа и моделируется как декодирование случайного ${\displaystyle (N,l)}$ линейного кода. Аналогично базовым корреляционным атакам, этот подкласс использует понятие расстояния Хэмминга.

Цель данной атаки — восстановление исходного состояния регистра сдвига (нахождение ключа), используя известную схему устройства и фрагмент шифрующей последовательности. Сложность атаки зависит от размера шифра и длины перехваченной гаммы.

Состоит из двух этапов:

1. построение большого словаря, в котором записаны всевозможные пары «состояние-выход»;
2. предположение о начальном заполнении регистра сдвига, генерация выхода, просмотр перехваченной выходной последовательности и поиск соответствия со сгенерированным выходом. Если произошло совпадение, то данное предположительное заполнение с большой вероятностью является начальным.

Примерами этого класса атак являются атака Стива Беббиджа и атака Бирюкова-Шамира.

Атака основывается на предположении, что криптоаналитику известны гамма, полином обратной связи, количество сдвигов регистра между выходами схемы и фильтрующая функция. Состоит из трёх этапов:

1. предположение о заполнении некоторых ячеек регистра;
2. определение полного заполнения регистра на основании предположения о знании криптоаналитика;
3. генерация выходной последовательности; если она совпадает с гаммой, то предположение на первом этапе было верно; если не совпадает, то возвращаемся к этапу 1.

Сложность алгоритма зависит от устройства генератора и от количества предположений.