Самосинхронизирующийся потоковый шифр

Самосинхронизирующиеся потоковые шифры (англ. Self-synchronizing stream ciphers, SSSC) — разновидность потоковых шифров, в которых открытый текст шифруется в зависимости от функции ключа и фиксированного числа знаков M шифртекста. Поэтому, каждый зашифрованный символ может быть дешифрован, если корректно были получены предыдущие M символов шифртекста, и функция ключа известна. Данный подход позволяет приемной стороне расшифровывать данные в асинхронном режиме, то есть не требует синхронизации генератора ключей приемной и передающей стороны.

Структура шифра

Шифрование очередного бита открытого текста $m_{i}$ производится за счет операции двоичного сложения с соответствующим битом ключа $z_{i}$:

$c_{i}=m_{i}\oplus z_{i}$,

где бит ключа $z_{i}$ определяется функцией шифрования $f_{s}$, зависящей от меняющегося по определенному правилу ключа шифрования K и от предшествующих M символов шифртекста, смещенных на b бит:

$z_{i}=f_{s}[K](c_{i-b-M+1}...c_{i-b})$

M называют памятью шифрования, а b - задержкой функции шифрования. Необходимость задержки b связана с тем, что при реализации алгоритма процессы отправления/получения зашифрованного текста и шифрования/расшифрования происходят параллельно. Расшифровка осуществляется следующим образом:

$m_{i}=c_{i}\oplus z_{i}$

Важно отметить, что для расшифровки первых M бит открытого текста необходимо определить вектор инициализации:

$C_{init}=c_{-M+1}...c_{0}$

Этот вектор должен быть отправлен получателю первым. При этом, если первые k бит вектора инициализации на приемной стороне отличаются от первых k бит передающей стороны, то вероятность того, что весь шифртекст получен корректно, равна $2^{-k}$.

Криптографические свойства

Криптографические свойства самосинхронизирующегося потокового шифра следуют из свойств функции шифрования. В рассматриваемой модели криптоаналитик знает память шифрования M функции шифрования $f_{s}$, а ключ K ему не известнен. Для обеспечения определенного уровня криптографической стойкости функции $f_{s}$, необходимо подобрать величину памяти шифрования M в зависимости от частоты сменяемости ключа K. Если на выходе функции криптоаналитик обнаружит две повторяющиеся последовательности шифртекста, длинной M каждая, то он сможет узнать сумму по модулю 2 соответствующих двух бит открытого текста.

Пусть получена последовательность шифртекста функции шифрования $f_{s}$ при одном ключе K :

$[c_{1}c_{2}...c_{M}]c_{M+1}...[c_{L+1}c_{L+2}...c_{L+M}]c_{L+M+1},L>M+1$

Без ограничения общности предположим, что задержка b=0.

$c_{M+1}=f_{s}[K](c_{1}c_{2}...c_{M})\oplus m_{M+1}$

$c_{L+M+1}=f_{s}[K](c_{L+1}c_{L+2}...c_{L+M})\oplus m_{L+M+1}$

При заданном условии $[c_{1}c_{2}...c_{M}]=[c_{L+1}c_{L+2}...c_{L+M}]$

$c_{M+1}\oplus c_{L+M+1}=m_{M+1}\oplus m_{L+M+1}$

Определим минимальное значение памяти шифра M, чтобы предотвратить описанную уязвимость. Рассмотрим поток шифртекста как последовательность случайных чисел. Вероятность q(N, M) того, что в случайной бинарной последовательности длины N все подпоследовательности длины M различны, равна:

$q(N,M)=\prod _{i=0}^{N-1}(1-i2^{-M})$

Воспользовавшись разложением Тэйлора $\ln(1-x)\approx -x$ для малых x, получим:

$\ln q(N,M)=\sum _{i=0}^{N-1}\ln(1-i2^{-M})\approx -2^{-M}\sum _{i=0}^{N-1}i=-N(N-1)2^{-M-1}$

Зададим допустимую вероятность p повторения 2-х подпоследовательностей длины M внутри последовательности длины N. Длина последовательности N задается при одном ключе K функци шифровани $f_{s}$.

$p<1-q(N,M)\approx \ln q(N,M)$

Отсюда находим, что память шифрования M должна быть выбрана:

$M\geqslant \log _{2}({\frac {N^{2}}{p}})$

Например, для $p=10^{-9}$ и $N=10^{12}$, оценка на память шифрования - $M\geqslant 110$. С другой стороны, следует учесть возможность появлений ошибок при передачи данных по каналу связи. Ошибка в одном бите при передаче шифртекста распространяется на следующие M бит при расшифровке.Следовательно, память шифрования M должна быть выбрана как можно меньше. Учитывая приведенные аргументы, для конкретного примера выбрать $M\in [80,128]$ кажется разумным для удовлетворения условий безопасности и устойчивости к ошибкам.

Сравнение самосинхронизирующихся поточных шифров с аналогами

Сравнение с синхронными поточными шифрами

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

Сравнение с блочным шифром

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