Interested Article - F-FCSR

F-FCSR — семейство поточных шифров , основанное на использовании регистра сдвига с обратной связью по переносу (FCSR) с линейным фильтром на выходе. Идея шифра была предложена Терри Бергером, Франсуа Арно и Седриком Лараду. F-FCSR был представлен на конкурсе eSTREAM , был включен в список победителей конкурса в апреле 2008, но в дальнейшем была выявлена криптографическая слабость и в сентябре 2008 F-FCSR был исключён из списка eSTREAM.

История

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

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

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

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

Характеристики версий

Название	Длина главного регистра	Инициализация	Фильтр	Число бит на выходе фильтра
F-FCSR-8	128	64/128 тактов (в зависимости от IV)	Зависит от ключа	8
F-FCSR-H	160	160 тактов	Статический	8
F-FCSR-8.2	256	258 тактов	Зависит от ключа	16
F-FCSR-16	256	16 + 258 тактов	Статический	16
F-FCSR-H v.2	160	20 + 162 такта	Статический	8

Описание алгоритма

FCSR

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

q — целостность соединения (connection integer) — отрицательное нечетное целое число, удовлетворяющее следующим условиям:
- $2^{|q|-1}=1\mod {q}$ $2^{|q|-1}=1\mod {q}$
- T = (|q| − 1)/2 — простое, 2T — период битовой последовательности p/q
- Число единиц в двоичном представлении числа (1 − q)/2 порядка n/2
p — параметр, зависящий от ключа, такое, что 0 < p < |q|
n — размер главного регистра FCSR, |q| в двоичной записи имеет n + 1 знаков: 2 ⁿ < −q < 2 ⁿ⁺¹
d : d = (1 − q)/2, в двоичной записи $\sum _{i=0}^{n-1}d_{i}\cdot 2^{i}$ $\sum _{i=0}^{n-1}d_{i}\cdot 2^{i}$ , d _i = {0, 1}, d _n-1 = 1
M — n-разрядный главный регистр, значения его i-го разряда, $m(t)=\sum _{i=0}^{n-1}m_{i}(t)\cdot 2^{i}$ $m(t)=\sum _{i=0}^{n-1}m_{i}(t)\cdot 2^{i}$ .
C — l-разрядный регистр сдвига, l + 1 — число единиц в двоичной записи d, $c(t)=\sum _{i=0}^{l-1}c_{i}(t)\cdot 2^{i}$ $c(t)=\sum _{i=0}^{l-1}c_{i}(t)\cdot 2^{i}$ .
(m, c) — состояние FCSR

Если (m, c) — состояние FCSR в момент времени t ₀ , $m=m(t_{0})$ $m=m(t_{0})$ , $c=c(t_{0})$ $c=c(t_{0})$ , то $(m_{0}(t_{0}+i))_{i\in {N}}$ $(m_{0}(t_{0}+i))_{i\in {N}}$ — двоичное представление p/q, где p = m + 2c.

Пример FCSR

q = −347, d = 174 = (10101110) ₂ , n = 8, l = 4.

Фильтрация

Фильтрующая линейная функция на выходе определяется маской ( ${f}_{0,}{f}_{1,...,}{f}_{n-1}$ ${f}_{0,}{f}_{1,...,}{f}_{n-1}$ ) Один бит на выходе определяется следующим образом: ${k}=\bigoplus _{i=0}^{n-1}{f}_{i}\cdot {m}_{i}$ ${k}=\bigoplus _{i=0}^{n-1}{f}_{i}\cdot {m}_{i}$

Инициализация

С учетом слабости предыдущих версий F-FCSR из-за слабого начального перемешивания битов в главном регистре процедура инициализации в F-FCSR-H v.2 и F-FCSR-16 проводится следующим образом:

Главный регистр M инициализируется конкатенацией секретного ключа K и IV — (K, IV), в регистр переноса записываются нули.
Проходит 16 тактов генератора для F-FCSR-16 и 20 для F-FCSR-H v.2
Полученные на выходе 256 и 160 битов соответственно записываются в M
Проходит n + 2 тактов генератора, биты на выходе при этом отбрасываются

Шифры на основе F-FCSR

F-FCSR-H v.2

Длина ключа 80 бит, IV — 80 бит
q = −1993524591318275015328041611344215036460140087963
Длина регистра переноса l = 82
d = (AE985DFF 26619FC5 8623DC8A AF46D590 3DD4254E) ₁₆
Последовательность битов на выходе ${S(t)}={(s}_{0}{(t),}{s}_{1}{(t),...}{s}_{7}{(t)),}s_{j}(t)=\bigoplus _{i=0}^{19}d_{8i+j}\cdot m_{8i+j}(t)$ ${S(t)}={(s}_{0}{(t),}{s}_{1}{(t),...}{s}_{7}{(t)),}s_{j}(t)=\bigoplus _{i=0}^{19}d_{8i+j}\cdot m_{8i+j}(t)$ , то есть

z = (m ₈ + m ₂₄ + m ₄₀ + m ₅₆ + … + m ₁₃₆ , m ₁ + m ₄₉ +… , … , m ₂₃ + …)

F-FCSR-16

Длина ключа 128 бит, IV — 128 бит
q = −183971440845619471129869161809344131658298317655923135753017128462155618715019
Длина регистра переноса l = 130
d = (CB5E129F AD4F7E66 780CAA2E C8C9CEDB 2102F996 BAF08F39 EFB55A6E 390002C6) ₁₆
Последовательность битов на выходе ${S(t)}={(s}_{0}{(t),}{s}_{1}{(t),...}{s}_{15}{(t)),}s_{j}(t)=\bigoplus _{i=0}^{15}d_{16i+j}\cdot m_{16i+j}(t)$ ${S(t)}={(s}_{0}{(t),}{s}_{1}{(t),...}{s}_{15}{(t)),}s_{j}(t)=\bigoplus _{i=0}^{15}d_{16i+j}\cdot m_{16i+j}(t)$

Описание атаки

Первоначально найденные уязвимости 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. Тогда для возникновения (*), потребуется приблизительно $\log _{2}{82}+19\approx 26$ $\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 неизвестными $m_{i}$ $m_i$ , где $i\equiv 0\mod 8$ $i\equiv 0\mod 8$ :

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

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

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

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

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

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

else сохраняем возможные значения ${\hat {M}}_{j}$ ${\hat {M}}_{j}$
for (каждый возможный набор ${\hat {M}}_{0},{\hat {M}}_{1}...{\hat {M}}_{7}$ ${\hat {M}}_{0},{\hat {M}}_{1}...{\hat {M}}_{7}$ )

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

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

Примечания

↑ A. Klapper, M. Goresky, 2-adic shift registers, in Fast Software Encryption’93, ed. by R.J. Anderson. Lecture Notes in Computer Science, vol. 809 (Springer, Berlin, 1994), pp. 174—178
F. Arnault, T. Berger, A. Necer, A new class of stream ciphers combining LFSR and FCSR architectures, in Progress in Cryptology—INDOCRYPT 2002, ed. by A. Menezes, P. Sarkar. Lecture Notes in Computer Science, vol. 2551/2002 (Springer, Berlin, 2002), pp. 22-33
B. Zhang, H.Wu, D. Feng, F. Bao, Chosen ciphertext attack on a new class of self-synchronizing stream ciphers, in Progress in Cryptology—INDOCRYPT 2004, ed. by A. Canteaut, K. Viswanathan. Lecture Notes in Computer Science, vol. 3348/2004 (Springer, Berlin, 2004), pp. 73-83
F. Arnault, T. Berger, Design and properties of a new pseudorandom generator based on a filtered FCSR automaton. IEEE Trans. Comput. 54, 1374—1383 (2005)
F. Arnault, T. Berger, F-FCSR: Design of a new class of stream ciphers, in Fast Software Encryption 2005, ed. by H. Gilbert, H. Handschuh. Lecture Notes in Computer Science, vol. 3557 (Springer, Berlin, 2005), pp. 83-97
E. Jaulmes, F. Muller, Cryptanalysis of the F-FCSR stream cipher family, in Selected Areas in Cryptography—SAC 2005, ed. by B. Preneel, S. Tavares. Lecture Notes in Computer Science, vol. 3897 (Springer, Berlin, 2005), pp. 36-50
(неопр.) . Дата обращения: 23 ноября 2011. 27 мая 2011 года.
(неопр.) . Дата обращения: 23 ноября 2011. 27 мая 2011 года.
(неопр.) . Дата обращения: 23 ноября 2011. 27 мая 2011 года.
(неопр.) . Дата обращения: 23 ноября 2011. 5 декабря 2011 года.
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
(неопр.) . Дата обращения: 23 ноября 2011. 13 августа 2012 года.

Литература

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
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.
F. Arnault, T. Berger, C. Lauradoux, Update on F-FCSR stream cipher. eSTREAM, ECRYPT Stream Cipher Project, Report 2006/025 (2006).

Ссылки

[autogenerated1-1] A. Klapper, M. Goresky, 2-adic shift registers, in Fast Software Encryption’93, ed. by R.J. Anderson. Lecture Notes in Computer Science, vol. 809 (Springer, Berlin, 1994), pp. 174—178

[2] F. Arnault, T. Berger, A. Necer, A new class of stream ciphers combining LFSR and FCSR architectures, in Progress in Cryptology—INDOCRYPT 2002, ed. by A. Menezes, P. Sarkar. Lecture Notes in Computer Science, vol. 2551/2002 (Springer, Berlin, 2002), pp. 22-33

[3] B. Zhang, H.Wu, D. Feng, F. Bao, Chosen ciphertext attack on a new class of self-synchronizing stream ciphers, in Progress in Cryptology—INDOCRYPT 2004, ed. by A. Canteaut, K. Viswanathan. Lecture Notes in Computer Science, vol. 3348/2004 (Springer, Berlin, 2004), pp. 73-83

[4] F. Arnault, T. Berger, Design and properties of a new pseudorandom generator based on a filtered FCSR automaton. IEEE Trans. Comput. 54, 1374—1383 (2005)

[5] F. Arnault, T. Berger, F-FCSR: Design of a new class of stream ciphers, in Fast Software Encryption 2005, ed. by H. Gilbert, H. Handschuh. Lecture Notes in Computer Science, vol. 3557 (Springer, Berlin, 2005), pp. 83-97

[6] E. Jaulmes, F. Muller, Cryptanalysis of the F-FCSR stream cipher family, in Selected Areas in Cryptography—SAC 2005, ed. by B. Preneel, S. Tavares. Lecture Notes in Computer Science, vol. 3897 (Springer, Berlin, 2005), pp. 36-50

[7] (неопр.) . Дата обращения: 23 ноября 2011. 27 мая 2011 года.

[8] (неопр.) . Дата обращения: 23 ноября 2011. 27 мая 2011 года.

[9] (неопр.) . Дата обращения: 23 ноября 2011. 27 мая 2011 года.

[10] (неопр.) . Дата обращения: 23 ноября 2011. 5 декабря 2011 года.

[11] 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

[12] (неопр.) . Дата обращения: 23 ноября 2011. 13 августа 2012 года.