Просмотр кода страницы F-FCSR

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

== История ==
Впервые идея использования регистра сдвига с обратной связью по переносу (FCSR) для создания поточного фильтра была предложена Клаппером и Горески в 1994 году<ref name=autogenerated1>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</ref>. Позднее ими был разработан алгоритм такого шифра<ref name=autogenerated1 />. Один FCSR без подключения линейного компонента не может быть использован в качестве поточного шифра, так как легко дешифруется.

В 2002 году был предложен самосинхронизующийся поточный шифр, основанный на совместном использовании FCSR и LFSR<ref>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</ref>. Позднее он был подвергнут атаке с выбором шифротекста<ref>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</ref>.

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

В 2005 Терри Бергер, Франсуа Арноль и Седрик Лараду предложили два шифра на основе F-FCSR<ref>{{Cite web |url=http://www.ecrypt.eu.org/stream/ciphers/ffcsr/ffcsr.zip |title=Архивированная копия |access-date=2011-11-23 |archive-date=2011-05-27 |archive-url=https://web.archive.org/web/20110527072025/http://www.ecrypt.eu.org/stream/ciphers/ffcsr/ffcsr.zip |deadlink=no }}</ref> для участия в конкурсе eSTREAM: F-FCSR-H для аппаратной реализации и F-FCSR-8 для программной. В результате последующих испытаний у первоначальных версий F-FCSR-H и F-FCSR-8 были найдены уязвимости<ref>{{Cite web |url=http://www.ecrypt.eu.org/stream/papersdir/046.ps |title=Архивированная копия |access-date=2011-11-23 |archive-date=2011-05-27 |archive-url=https://web.archive.org/web/20110527071941/http://www.ecrypt.eu.org/stream/papersdir/046.ps |deadlink=no }}</ref>, которые позже были исправлены в версиях F-FCSR-H v.2 и F-FCSR-16<ref>{{Cite web |url=http://www.ecrypt.eu.org/stream/papersdir/2006/025.pdf |title=Архивированная копия |access-date=2011-11-23 |archive-date=2011-05-27 |archive-url=https://web.archive.org/web/20110527072047/http://www.ecrypt.eu.org/stream/papersdir/2006/025.pdf |deadlink=no }}</ref>. Улучшенный вариант F-FCSR-H v.2 стал финалистом eSTREAM<ref>{{Cite web |url=http://www.ecrypt.eu.org/stream/endofphase3.html |title=The eSTREAM Project<!-- Заголовок добавлен ботом --> |access-date=2011-11-23 |archive-date=2011-12-05 |archive-url=https://web.archive.org/web/20111205043033/http://www.ecrypt.eu.org/stream/endofphase3.html |deadlink=no }}</ref>. Но после обнаружения уязвимости<ref>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</ref> был исключен из eSTREAM Portfolio (rev.1)<ref>{{Cite web |url=http://www.ecrypt.eu.org/stream/portfolio_revision1.pdf |title=Архивированная копия |access-date=2011-11-23 |archive-date=2012-08-13 |archive-url=https://web.archive.org/web/20120813111955/http://www.ecrypt.eu.org/stream/portfolio_revision1.pdf |deadlink=no }}</ref>.

=== Характеристики версий ===
{| class="wikitable"
|-
! Название !! Длина главного <br>регистра !! Инициализация !! Фильтр !! Число бит <br>на выходе фильтра
|-
|F-FCSR-8 || 128 || 64/128 тактов<br>(в зависимости от 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 используется конфигурация Галуа, так как она эффективней.
Вводятся следующие обозначения:
# <big>'''q'''</big> — целостность соединения (connection integer) — отрицательное нечетное целое число, удовлетворяющее следующим условиям:
#* <math>2^{|q|-1} = 1\mod{q}</math>
#* T = (|q| − 1)/2 — простое, 2T — период битовой последовательности p/q
#* Число единиц в двоичном представлении числа (1 − q)/2 порядка n/2
# <big>'''p'''</big> — параметр, зависящий от ключа, такое, что 0 < p < |q|
# <big>'''n'''</big> — размер главного регистра FCSR, |q| в двоичной записи имеет n + 1 знаков: 2<sup>n</sup> < −q < 2<sup>n+1</sup>
# <big>'''d'''</big>: d = (1 − q)/2, в двоичной записи <math>\sum^{n - 1}_{i=0} d_{i} \cdot 2 ^ i</math>, d<sub>i</sub> = {0, 1}, d<sub>n-1</sub> = 1
# <big>'''M'''</big> — n-разрядный главный регистр, значения его i-го разряда, <math>m(t) = \sum^{n - 1}_{i=0} m_{i}(t) \cdot 2 ^ i</math>.
# <big>'''C'''</big> — l-разрядный регистр сдвига, l + 1 — число единиц в двоичной записи d, <math>c(t) = \sum^{l - 1}_{i=0} c_{i}(t) \cdot 2 ^ i</math>.
# '''(m, c)''' — состояние FCSR
Если (m, c) — состояние FCSR в момент времени t<sub>0</sub>, <big><big><math>m = m(t_0)</math></big></big>, <big><big><math>c = c(t_0)</math></big></big>, то <math>(m_0(t_0 + i))_{i\in{N}}</math> — двоичное представление p/q, где p = m + 2c.

==== Пример FCSR ====
[[Файл:FCSR2.png|512px|thumb|Пример FCSR]]

q = −347, d = 174 = (10101110)<sub>2</sub>, n = 8, l = 4.

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

=== Инициализация ===
С учетом слабости предыдущих версий 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)<sub>16</sub>
# Последовательность битов на выходе <math>{S(t)} = {(s}_0{(t), }{s}_1{(t), ... }{s}_7{(t)), }s_{j}(t) = \bigoplus^{19}_{i=0} d_{8i+j} \cdot m_{8i+j}(t)</math>, то есть<br>
:: <big>z = (m<sub>8</sub> + m<sub>24</sub> + m<sub>40</sub> + m<sub>56</sub> + … + m<sub>136</sub>, m<sub>1</sub> + m<sub>49</sub> +… , … , m<sub>23</sub> + …)</big>

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

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

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

<big>'''C(t) = C(t + 1)= … = C(t + 19) = (С<sub>l-1</sub>, …, С<sub>0</sub>) = (0, 0, . . . , 0, 1) (*)'''</big>

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

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

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

Выразим <big>'''z(t), z(t + 1), … , z(t + 19)'''</big> через значения битов главного регистра в момент t: '''<big>M(t) = (m<sub>0</sub> … m<sub>159</sub>)</big>'''. <br> Получим 20 уравнений с 20 неизвестными <big><big><math>m_i</math></big></big>, где <math>i\equiv0\mod8</math>:<br><br>
<math>z_0(t)=m_8\bigoplus{m_{24}}\bigoplus{...}\bigoplus{m_{136}}</math> <br><br>
<math>z_7(t+1)=m_{24}\bigoplus{m_{40}}\bigoplus{...}\bigoplus{m_{152}}</math> <br>
…<br>
<math>z_{5}(t+19)=m_{32}\bigoplus{m_{48}}\bigoplus{...}\bigoplus{m_{152}}</math> <br><br>
Аналогично получим системы уравнений, зависящих от <big><big><math>m_i</math></big></big>, где <math>i\equiv1\mod8</math> и т. д. <br>Итого 8 систем из 20 уравнений с 20 неизвестными.<br>
Ведем следующие обозначения:<br>
<big><big><math>W_0 = (z_0(t), z_7(t + 1), . . . , z_5(t + 19))</math>,<br>
<math>W_1 = (z_1(t), z_0(t + 1), . . . , z_6(t +19))</math>, <br>
… <br>
<math>W_7 = (z_7(t), z_6(t + 1), . . . , z_4(t +19))</math>. <br></big>
</big>
Обозначим <big><math>\hat{M}_j</math></big> вектор <big><big><math>(m_j, m_{j+8}, ..., m_{j+152})</math></big></big> <br>
Тогда системы сожно записать в виде <big><math>W_j = \hat{M}_jP_j</math></big>, где <big><big><math>P_j</math></big></big> — известная матрица, определяемая фильтрующей функцией.
Алгоритм нахождения состояния главного регистра в предположении(*) можно описать следующим образом:
# В момент времени t получаем на выходе байты: <big>'''z(t), z(t +1), . . . , z(t + 19)'''</big>
# '''for''' i = 0 '''to''' 7
#: Решаем уравнение <big><math>W_j = \hat{M}_jP_j</math></big>
#: '''if''' (нет решений) '''goto''' 1
#: '''else''' сохраняем возможные значения <big><math>\hat{M}_j</math></big>
# '''for''' (каждый возможный набор <big><math>\hat{M}_0, \hat{M}_1...\hat{M}_7</math></big>)
#: '''if''' (M из<big><math>\hat{M}_0, \hat{M}_1...\hat{M}_7</math></big> может дать на выходе <big>'''z(t), z(t +1), . . . , z(t + 19)'''</big>) '''return''';
# '''goto''' 1
Для осуществления описанной выше атаки требуется 2<sup>26</sup> байт шифротекста. Возможно улучшение атаки, требуюшее 2<sup>24,3</sup> байта. Аналогичная атака может быть применена к F-FCSR-16.

== Примечания ==
{{примечания|2}}

== Литература ==
# 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).

== Ссылки ==
* http://www.ecrypt.eu.org/stream/index.html

{{Симметричные криптосистемы}}

[[Категория:Потоковые шифры]]