F-FCSR

Поделись знанием:
Перейти к: навигация, поиск

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





История

Впервые идея использования регистра сдвига с обратной связью по переносу (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 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 используется конфигурация Галуа, так как она эффективней. Вводятся следующие обозначения:

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

Если (m, c) — состояние FCSR в момент времени t0, <math>m = m(t_0)</math>, <math>c = c(t_0)</math>, то <math>(m_0(t_0 + i))_{i\in{N}}</math> — двоичное представление p/q, где p = m + 2c.

Пример FCSR


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

Фильтрация

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

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

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

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

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

F-FCSR-H v.2

  1. Длина ключа 80 бит, IV — 80 бит
  2. q = −1993524591318275015328041611344215036460140087963
  3. Длина регистра переноса l = 82
  4. d = (AE985DFF 26619FC5 8623DC8A AF46D590 3DD4254E)16
  5. Последовательность битов на выходе <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>, то есть
z = (m8 + m24 + m40 + m56 + … + m136, m1 + m49 +… , … , m23 + …)

F-FCSR-16

  1. Длина ключа 128 бит, IV — 128 бит
  2. q = −183971440845619471129869161809344131658298317655923135753017128462155618715019
  3. Длина регистра переноса l = 130
  4. d = (CB5E129F AD4F7E66 780CAA2E C8C9CEDB 2102F996 BAF08F39 EFB55A6E 390002C6)16
  5. Последовательность битов на выходе <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 тактов будет следующим:

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

Если бит обратной связи 0, то биты регистра переноса, равные 0, остаются равны 0, а равные 1 с вероятностью ½ становятся равны 0. Тогда для возникновения (*), потребуется приблизительно <math>\log_2{82} + 19 \approx 26</math> последовательных нулей в бите обратной связи.
В силу предположения (*) состояния главного регистра 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) = (m0 … m159).
Получим 20 уравнений с 20 неизвестными <math>m_i</math>, где <math>i\equiv0\mod8</math>:

<math>z_0(t)=m_8\bigoplus{m_{24}}\bigoplus{...}\bigoplus{m_{136}}</math>

<math>z_7(t+1)=m_{24}\bigoplus{m_{40}}\bigoplus{...}\bigoplus{m_{152}}</math>

<math>z_{5}(t+19)=m_{32}\bigoplus{m_{48}}\bigoplus{...}\bigoplus{m_{152}}</math>

Аналогично получим системы уравнений, зависящих от <math>m_i</math>, где <math>i\equiv1\mod8</math> и т. д.
Итого 8 систем из 20 уравнений с 20 неизвестными.
Ведем следующие обозначения:
<math>W_0 = (z_0(t), z_7(t + 1), . . . , z_5(t + 19))</math>,
<math>W_1 = (z_1(t), z_0(t + 1), . . . , z_6(t +19))</math>,

<math>W_7 = (z_7(t), z_6(t + 1), . . . , z_4(t +19))</math>.
Обозначим <math>\hat{M}_j</math> вектор <math>(m_j, m_{j+8}, ..., m_{j+152})</math>
Тогда системы сожно записать в виде <math>W_j = \hat{M}_jP_j</math>, где <math>P_j</math> — известная матрица, определяемая фильтрующей функцией. Алгоритм нахождения состояния главного регистра в предположении(*) можно описать следующим образом:

  1. В момент времени t получаем на выходе байты: z(t), z(t +1), . . . , z(t + 19)
  2. for i = 0 to 7
    Решаем уравнение <math>W_j = \hat{M}_jP_j</math>
    if (нет решений) goto 1
    else сохраняем возможные значения <math>\hat{M}_j</math>
  3. for (каждый возможный набор <math>\hat{M}_0, \hat{M}_1...\hat{M}_7</math>)
    if (M из<math>\hat{M}_0, \hat{M}_1...\hat{M}_7</math> может дать на выходе z(t), z(t +1), . . . , z(t + 19)) return;
  4. goto 1

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

Напишите отзыв о статье "F-FCSR"

Примечания

  1. 1 2 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. www.ecrypt.eu.org/stream/ciphers/ffcsr/ffcsr.zip
  8. www.ecrypt.eu.org/stream/papersdir/046.ps
  9. www.ecrypt.eu.org/stream/papersdir/2006/025.pdf
  10. [www.ecrypt.eu.org/stream/endofphase3.html The eSTREAM Project]
  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. www.ecrypt.eu.org/stream/portfolio_revision1.pdf

Литература

  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).

Ссылки

www.ecrypt.eu.org/stream/index.html

Отрывок, характеризующий F-FCSR

Толпа подошла к большому столу, у которого, в мундирах, в лентах, седые, плешивые, сидели семидесятилетние вельможи старики, которых почти всех, по домам с шутами и в клубах за бостоном, видал Пьер. Толпа подошла к столу, не переставая гудеть. Один за другим, и иногда два вместе, прижатые сзади к высоким спинкам стульев налегающею толпой, говорили ораторы. Стоявшие сзади замечали, чего не досказал говоривший оратор, и торопились сказать это пропущенное. Другие, в этой жаре и тесноте, шарили в своей голове, не найдется ли какая мысль, и торопились говорить ее. Знакомые Пьеру старички вельможи сидели и оглядывались то на того, то на другого, и выражение большей части из них говорило только, что им очень жарко. Пьер, однако, чувствовал себя взволнованным, и общее чувство желания показать, что нам всё нипочем, выражавшееся больше в звуках и выражениях лиц, чем в смысле речей, сообщалось и ему. Он не отрекся от своих мыслей, но чувствовал себя в чем то виноватым и желал оправдаться.
– Я сказал только, что нам удобнее было бы делать пожертвования, когда мы будем знать, в чем нужда, – стараясь перекричать другие голоса, проговорил он.
Один ближайший старичок оглянулся на него, но тотчас был отвлечен криком, начавшимся на другой стороне стола.
– Да, Москва будет сдана! Она будет искупительницей! – кричал один.
– Он враг человечества! – кричал другой. – Позвольте мне говорить… Господа, вы меня давите…


В это время быстрыми шагами перед расступившейся толпой дворян, в генеральском мундире, с лентой через плечо, с своим высунутым подбородком и быстрыми глазами, вошел граф Растопчин.
– Государь император сейчас будет, – сказал Растопчин, – я только что оттуда. Я полагаю, что в том положении, в котором мы находимся, судить много нечего. Государь удостоил собрать нас и купечество, – сказал граф Растопчин. – Оттуда польются миллионы (он указал на залу купцов), а наше дело выставить ополчение и не щадить себя… Это меньшее, что мы можем сделать!
Начались совещания между одними вельможами, сидевшими за столом. Все совещание прошло больше чем тихо. Оно даже казалось грустно, когда, после всего прежнего шума, поодиночке были слышны старые голоса, говорившие один: «согласен», другой для разнообразия: «и я того же мнения», и т. д.
Было велено секретарю писать постановление московского дворянства о том, что москвичи, подобно смолянам, жертвуют по десять человек с тысячи и полное обмундирование. Господа заседавшие встали, как бы облегченные, загремели стульями и пошли по зале разминать ноги, забирая кое кого под руку и разговаривая.
– Государь! Государь! – вдруг разнеслось по залам, и вся толпа бросилась к выходу.
По широкому ходу, между стеной дворян, государь прошел в залу. На всех лицах выражалось почтительное и испуганное любопытство. Пьер стоял довольно далеко и не мог вполне расслышать речи государя. Он понял только, по тому, что он слышал, что государь говорил об опасности, в которой находилось государство, и о надеждах, которые он возлагал на московское дворянство. Государю отвечал другой голос, сообщавший о только что состоявшемся постановлении дворянства.
– Господа! – сказал дрогнувший голос государя; толпа зашелестила и опять затихла, и Пьер ясно услыхал столь приятно человеческий и тронутый голос государя, который говорил: – Никогда я не сомневался в усердии русского дворянства. Но в этот день оно превзошло мои ожидания. Благодарю вас от лица отечества. Господа, будем действовать – время всего дороже…
Государь замолчал, толпа стала тесниться вокруг него, и со всех сторон слышались восторженные восклицания.
– Да, всего дороже… царское слово, – рыдая, говорил сзади голос Ильи Андреича, ничего не слышавшего, но все понимавшего по своему.
Из залы дворянства государь прошел в залу купечества. Он пробыл там около десяти минут. Пьер в числе других увидал государя, выходящего из залы купечества со слезами умиления на глазах. Как потом узнали, государь только что начал речь купцам, как слезы брызнули из его глаз, и он дрожащим голосом договорил ее. Когда Пьер увидал государя, он выходил, сопутствуемый двумя купцами. Один был знаком Пьеру, толстый откупщик, другой – голова, с худым, узкобородым, желтым лицом. Оба они плакали. У худого стояли слезы, но толстый откупщик рыдал, как ребенок, и все твердил:
– И жизнь и имущество возьми, ваше величество!
Пьер не чувствовал в эту минуту уже ничего, кроме желания показать, что все ему нипочем и что он всем готов жертвовать. Как упрек ему представлялась его речь с конституционным направлением; он искал случая загладить это. Узнав, что граф Мамонов жертвует полк, Безухов тут же объявил графу Растопчину, что он отдает тысячу человек и их содержание.
Старик Ростов без слез не мог рассказать жене того, что было, и тут же согласился на просьбу Пети и сам поехал записывать его.
На другой день государь уехал. Все собранные дворяне сняли мундиры, опять разместились по домам и клубам и, покряхтывая, отдавали приказания управляющим об ополчении, и удивлялись тому, что они наделали.



Наполеон начал войну с Россией потому, что он не мог не приехать в Дрезден, не мог не отуманиться почестями, не мог не надеть польского мундира, не поддаться предприимчивому впечатлению июньского утра, не мог воздержаться от вспышки гнева в присутствии Куракина и потом Балашева.
Александр отказывался от всех переговоров потому, что он лично чувствовал себя оскорбленным. Барклай де Толли старался наилучшим образом управлять армией для того, чтобы исполнить свой долг и заслужить славу великого полководца. Ростов поскакал в атаку на французов потому, что он не мог удержаться от желания проскакаться по ровному полю. И так точно, вследствие своих личных свойств, привычек, условий и целей, действовали все те неперечислимые лица, участники этой войны. Они боялись, тщеславились, радовались, негодовали, рассуждали, полагая, что они знают то, что они делают, и что делают для себя, а все были непроизвольными орудиями истории и производили скрытую от них, но понятную для нас работу. Такова неизменная судьба всех практических деятелей, и тем не свободнее, чем выше они стоят в людской иерархии.
Теперь деятели 1812 го года давно сошли с своих мест, их личные интересы исчезли бесследно, и одни исторические результаты того времени перед нами.
Но допустим, что должны были люди Европы, под предводительством Наполеона, зайти в глубь России и там погибнуть, и вся противуречащая сама себе, бессмысленная, жестокая деятельность людей – участников этой войны, становится для нас понятною.
Провидение заставляло всех этих людей, стремясь к достижению своих личных целей, содействовать исполнению одного огромного результата, о котором ни один человек (ни Наполеон, ни Александр, ни еще менее кто либо из участников войны) не имел ни малейшего чаяния.
Теперь нам ясно, что было в 1812 м году причиной погибели французской армии. Никто не станет спорить, что причиной погибели французских войск Наполеона было, с одной стороны, вступление их в позднее время без приготовления к зимнему походу в глубь России, а с другой стороны, характер, который приняла война от сожжения русских городов и возбуждения ненависти к врагу в русском народе. Но тогда не только никто не предвидел того (что теперь кажется очевидным), что только этим путем могла погибнуть восьмисоттысячная, лучшая в мире и предводимая лучшим полководцем армия в столкновении с вдвое слабейшей, неопытной и предводимой неопытными полководцами – русской армией; не только никто не предвидел этого, но все усилия со стороны русских были постоянно устремляемы на то, чтобы помешать тому, что одно могло спасти Россию, и со стороны французов, несмотря на опытность и так называемый военный гений Наполеона, были устремлены все усилия к тому, чтобы растянуться в конце лета до Москвы, то есть сделать то самое, что должно было погубить их.
В исторических сочинениях о 1812 м годе авторы французы очень любят говорить о том, как Наполеон чувствовал опасность растяжения своей линии, как он искал сражения, как маршалы его советовали ему остановиться в Смоленске, и приводить другие подобные доводы, доказывающие, что тогда уже будто понята была опасность кампании; а авторы русские еще более любят говорить о том, как с начала кампании существовал план скифской войны заманивания Наполеона в глубь России, и приписывают этот план кто Пфулю, кто какому то французу, кто Толю, кто самому императору Александру, указывая на записки, проекты и письма, в которых действительно находятся намеки на этот образ действий. Но все эти намеки на предвидение того, что случилось, как со стороны французов так и со стороны русских выставляются теперь только потому, что событие оправдало их. Ежели бы событие не совершилось, то намеки эти были бы забыты, как забыты теперь тысячи и миллионы противоположных намеков и предположений, бывших в ходу тогда, но оказавшихся несправедливыми и потому забытых. Об исходе каждого совершающегося события всегда бывает так много предположений, что, чем бы оно ни кончилось, всегда найдутся люди, которые скажут: «Я тогда еще сказал, что это так будет», забывая совсем, что в числе бесчисленных предположений были делаемы и совершенно противоположные.