F-FCSR

Впервые идея использования регистра сдвига с обратной связью по переносу (FCSR) для создания поточного фильтра была предложена Клаппером и Горески в 1994 году[1]. Позднее ими был разработан алгоритм такого шифра[1]. Один FCSR без подключения линейного компонента не может быть использован в качестве поточного шифра, так как легко дешифруется.

В 2002 году был предложен самосинхронизующийся поточный шифр, основанный на совместном использовании FCSR и LFSR[2]. Позднее он был подвергнут атаке с выбором шифротекста[3].

В 2005 году Арно и Бергер предложили идею совместного использования FCSR и линейного фильтра для создания поточного шифра, который получил название F-FCSR (Filtered FCSR)[4]. Позже ими были предложены 4 алгоритма, реализующих эту идею: F-FCSR-SF1, F-FCSR-SF, F-FCSR-DF1 и F-FCSR-DF8[5]. Первые два использовали статические фильтры, последние — фильтры, зависящие от ключа. Позже была выявлена слабость всех этих алгоритмов перед различными видами атак[6].

В 2005 Терри Бергер, Франсуа Арноль и Седрик Лараду предложили два шифра на основе F-FCSR[7] для участия в конкурсе eSTREAM: F-FCSR-H для аппаратной реализации и F-FCSR-8 для программной. В результате последующих испытаний у первоначальных версий F-FCSR-H и F-FCSR-8 были найдены уязвимости[8], которые позже были исправлены в версиях F-FCSR-H v.2 и F-FCSR-16[9]. Улучшенный вариант F-FCSR-H v.2 стал финалистом eSTREAM[10]. Но после обнаружения уязвимости[11] был исключен из eSTREAM Portfolio (rev.1)[12].

Первоначально найденные уязвимости F-FCSR-8 и F-FCSR-H, связанные с малым количеством тактов при инициализации, были исправлены в F-FCSR-16 и F-FCSR-H v.2. В 2008 году Мартин Хелл и Томас Джоанссон описали и осуществили атаку на F-FCSR, с помощью которой можно вскрыть состояние FCSR.

Фильтрующая функция линейна, поэтому криптостойкость F-FCSR определяется нелинейностью FCSR, которая возникает из-за наличия регистра переноса, таким образом систему требуется линеаризовать, максимльно увеличив число нулей в регистре переноса. Рассмотрим ситуацию, когда состояние регистра переноса на протяжении 20 тактов будет следующим:

C(t) = C(t + 1)= … = C(t + 19) = (С_l-1, …, С₀) = (0, 0, . . . , 0, 1) (*)

Если бит обратной связи 0, то биты регистра переноса, равные 0, остаются равны 0, а равные 1 с вероятностью ½ становятся равны 0. Тогда для возникновения (*), потребуется приблизительно ${\displaystyle \log _{2}{82}+19\approx 26}$ последовательных нулей в бите обратной связи.

В силу предположения (*) состояния главного регистра M(t + 1), …, M(t + 19) линейно зависят от M(t), и нам известна эта зависимость.

Обозначим байты на выходе z(t), z(t + 1), … , z(t + 19).

Выразим z(t), z(t + 1), … , z(t + 19) через значения битов главного регистра в момент t: M(t) = (m₀ … m₁₅₉).
Получим 20 уравнений с 20 неизвестными ${\displaystyle m_{i}}$, где ${\displaystyle i\equiv 0\mod 8}$:

${\displaystyle z_{0}(t)=m_{8}\bigoplus {m_{24}}\bigoplus {...}\bigoplus {m_{136}}}$

${\displaystyle z_{7}(t+1)=m_{24}\bigoplus {m_{40}}\bigoplus {...}\bigoplus {m_{152}}}$
…
${\displaystyle z_{5}(t+19)=m_{32}\bigoplus {m_{48}}\bigoplus {...}\bigoplus {m_{152}}}$

Аналогично получим системы уравнений, зависящих от ${\displaystyle m_{i}}$, где ${\displaystyle i\equiv 1\mod 8}$ и т. д.
Итого 8 систем из 20 уравнений с 20 неизвестными.
Ведем следующие обозначения:
${\displaystyle W_{0}=(z_{0}(t),z_{7}(t+1),...,z_{5}(t+19))}$,
${\displaystyle W_{1}=(z_{1}(t),z_{0}(t+1),...,z_{6}(t+19))}$,
…
${\displaystyle W_{7}=(z_{7}(t),z_{6}(t+1),...,z_{4}(t+19))}$.
Обозначим ${\displaystyle {\hat {M}}_{j}}$ вектор ${\displaystyle (m_{j},m_{j+8},...,m_{j+152})}$
Тогда системы сожно записать в виде ${\displaystyle W_{j}={\hat {M}}_{j}P_{j}}$, где ${\displaystyle P_{j}}$ — известная матрица, определяемая фильтрующей функцией. Алгоритм нахождения состояния главного регистра в предположении(*) можно описать следующим образом:

1. В момент времени t получаем на выходе байты: z(t), z(t +1), . . . , z(t + 19)
2. for i = 0 to 7

   Решаем уравнение ${\displaystyle W_{j}={\hat {M}}_{j}P_{j}}$

   if (нет решений) goto 1

   else сохраняем возможные значения ${\displaystyle {\hat {M}}_{j}}$

3. for (каждый возможный набор ${\displaystyle {\hat {M}}_{0},{\hat {M}}_{1}...{\hat {M}}_{7}}$)

   if (M из${\displaystyle {\hat {M}}_{0},{\hat {M}}_{1}...{\hat {M}}_{7}}$ может дать на выходе z(t), z(t +1), . . . , z(t + 19)) return;

4. goto 1

Для осуществления описанной выше атаки требуется 2²⁶ байт шифротекста. Возможно улучшение атаки, требуюшее 2^24,3 байта. Аналогичная атака может быть применена к F-FCSR-16.

1. M. Hell, T. Johansson, Breaking the F-FCSR-H stream cipher in real time, in Advances in Cryptology. ASIACRYPT 2008. Lecture Notes in Computer Science, vol. 5350/2008 (Springer, Berlin, 2008), pp.557-569
2. F. Arnault and T.P. Berger. F-FCSR: design of a new class of stream ciphers. In Fast Software Encryption — FSE 2005, v. 3557 of Lecture Notes in Computer Science, p. 83-97. Springer-Verlag, 2005.
3. F. Arnault, T. Berger, C. Lauradoux, Update on F-FCSR stream cipher. eSTREAM, ECRYPT Stream Cipher Project, Report 2006/025 (2006).

• http://www.ecrypt.eu.org/stream/index.html