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

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

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

Шифрование очередного бита открытого текста [math]\displaystyle{ m_i }[/math] производится за счет операции двоичного сложения с соответствующим битом ключа [math]\displaystyle{ z_i }[/math]:

[math]\displaystyle{ c_i = m_i \oplus z_i }[/math],

где бит ключа [math]\displaystyle{ z_i }[/math] определяется функцией шифрования [math]\displaystyle{ f_s }[/math], зависящей от меняющегося по определённому правилу ключа шифрования [math]\displaystyle{ K }[/math] и от предшествующих [math]\displaystyle{ M }[/math] символов шифртекста, смещённых на [math]\displaystyle{ b }[/math] бит:

[math]\displaystyle{ z_i = f_s[K](c_{i-b-M+1} \dots c_{i-b}) }[/math]

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

[math]\displaystyle{ m_i = c_i \oplus z_i }[/math].

Для расшифровки первых [math]\displaystyle{ M }[/math] бит открытого текста необходимо определить вектор инициализации:

[math]\displaystyle{ C_{init} = c_{-M+1} \dots c_0 }[/math].

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

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

Криптографические свойства самосинхронизирующегося потокового шифра следуют из свойств функции шифрования. В рассматриваемой модели криптоаналитик знает память шифрования [math]\displaystyle{ M }[/math] функции шифрования [math]\displaystyle{ f_s }[/math], а ключ [math]\displaystyle{ K }[/math] ему неизвестен. Для обеспечения определённого уровня криптографической стойкости функции [math]\displaystyle{ f_s }[/math], необходимо подобрать величину памяти шифрования [math]\displaystyle{ M }[/math] в зависимости от частоты сменяемости ключа [math]\displaystyle{ K }[/math]. Если на выходе функции криптоаналитик обнаружит две повторяющиеся последовательности шифртекста длинной [math]\displaystyle{ M }[/math] каждая, то он сможет узнать сумму по модулю 2 соответствующих двух бит открытого текста.

Пусть получена последовательность шифртекста функции шифрования [math]\displaystyle{ f_s }[/math] при неменяющемся определённом ключе [math]\displaystyle{ K }[/math]:

[math]\displaystyle{ [c_1c_2...c_M]c_{M+1} \dots [c_{L+1}c_{L+2} \dots c_{L+M}]c_{L+M+1}, L\gt M+1 }[/math]

Без ограничения общности можно предположить нулевую задержку ([math]\displaystyle{ b = 0 }[/math]).

[math]\displaystyle{ c_{M+1} = f_s[K](c_1c_2 \dots c_M)\oplus m_{M+1} }[/math]

[math]\displaystyle{ c_{L+M+1} = f_s[K](c_{L+1}c_{L+2} \dots c_{L+M})\oplus m_{L+M+1} }[/math]

При заданном условии [math]\displaystyle{ [c_1c_2 \dots c_M] = [c_{L+1}c_{L+2} \dots c_{L+M}] }[/math]

[math]\displaystyle{ c_{M+1} \oplus c_{L+M+1} = m_{M+1}\oplus m_{L+M+1} }[/math]

Определяется минимальное значение памяти шифра [math]\displaystyle{ M }[/math], чтобы предотвратить описанную уязвимость. Если рассмотреть поток шифртекста как последовательность случайных чисел, вероятность [math]\displaystyle{ q(N, M) }[/math] того, что в случайной бинарной последовательности длины [math]\displaystyle{ N }[/math] все подпоследовательности длины [math]\displaystyle{ M }[/math] различны, равна:

[math]\displaystyle{ q(N, M) = \prod^{N-1}_{i=0}(1 - i2^{-M}) }[/math]

Воспользовавшись разложением Тэйлора [math]\displaystyle{ \ln(1-x)\approx -x }[/math] для малых [math]\displaystyle{ x }[/math], получается:

[math]\displaystyle{ \ln q(N, M) = \sum^{N-1}_{i=0}\ln(1 - i2^{-M})\approx -2^{-M}\sum^{N-1}_{i=0}i = -N(N - 1)2^{-M-1} }[/math]

Зададим допустимую вероятность p повторения 2-х подпоследовательностей длины M внутри последовательности длины N. Длина последовательности N задается при определённом ключе K функции шифрования [math]\displaystyle{ f_s }[/math].

[math]\displaystyle{ p \lt 1-q(N, M) \approx \ln q(N, M) }[/math]

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

[math]\displaystyle{ M \geqslant \log_2 (\frac{N^2}{p}) }[/math]

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

Дифференциальный криптоанализ

Для самосинхронизирующихся шифров может быть успешно применим дифференциальный криптоанализ, дающий ограничения на вид функции шифрования [math]\displaystyle{ f_s }[/math]. Для каждой пары входных векторов [math]\displaystyle{ C_1 }[/math] и [math]\displaystyle{ C_2 }[/math], длинной М, отличающиеся на [math]\displaystyle{ a' }[/math], функция [math]\displaystyle{ f_s }[/math] возвращает пару зашифрованных бит. Зафиксируем один входной вектор [math]\displaystyle{ C_1 }[/math]. Количество возможных отклонений [math]\displaystyle{ a' }[/math] от этого вектора: [math]\displaystyle{ N = 2^M - 1 }[/math] [math]\displaystyle{ (a \neq [00...0]) }[/math]. Рассмотрим пары [math]\displaystyle{ C_1 }[/math] и [math]\displaystyle{ C_2 = C_1 \oplus a' }[/math]. Определим дифференциальную вероятность [math]\displaystyle{ DP_{f_s}(a', 1) }[/math] того, что выходные биты равны : [math]\displaystyle{ f_s(C_1)=f_s(C_2) }[/math]. В дифференциальной криптоаналитеке рассматривают отличие [math]\displaystyle{ DP_f(a',1) }[/math] от [math]\displaystyle{ \frac{1}{2} }[/math]. Если дифференциальную вероятность можно представить в виде:

[math]\displaystyle{ DP_{f_s}(a', 1) = \frac{1}{2} \pm l^{-1} }[/math],

то число входных пар векторов, необходимых для вычисления разности [math]\displaystyle{ DP_{f_s}(a',1) - \frac{1}{2} }[/math] примерно равно [math]\displaystyle{ l^2 }[/math]. Отсюда следует, что функция шифрования не должна иметь дифференциальную вероятность [math]\displaystyle{ DP_{f_s}(a',1) }[/math], отличающихся от [math]\displaystyle{ \frac{1}{2} }[/math] более чем на [math]\displaystyle{ 2^{-\frac{M}{2}} }[/math]:

[math]\displaystyle{ l^{-1} = 2^{-\frac{M}{2}} }[/math]

Число необходимых пар:

[math]\displaystyle{ l^2 = 2^M \gt N = 2^M - 1 }[/math]

Таким образом, чтобы узнать разность [math]\displaystyle{ DP_{f_s}(a',1) - \frac{1}{2} }[/math], дающую информацию о ключе, необходимо полностью перебрать все возможные разности a'.

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

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

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

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

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

Литература

• Matthew Robshaw, Olivier Billet. New Stream Cipher Designs - The eSTREAM Finalists. — Springer. — 1997. — С. 210-216.
• Ueli M. Maurer. New Approaches to the Design of Self-Synchronizing Stream Ciphers // Advances in Cryptology — EUROCRYPT ’91. — Springer, Berlin, Heidelberg, 1991-04-08. — С. 459-466. — ISBN 3540464166.