F-FCSR — семейство поточных шифров, основанное на использовании регистра сдвига с обратной связью по переносу (FCSR) с линейным фильтром на выходе. Идея шифра была предложена Терри Бергером, Франсуа Арно и Седриком Лараду. F-FCSR был представлен на конкурсе eSTREAM, был включен в список победителей конкурса в апреле 2008, но в дальнейшем была выявлена криптографическая слабость и в сентябре 2008 F-FCSR был исключён из списка eSTREAM.
История Впервые идея использования регистра сдвига с обратной связью по переносу (FCSR) для создания поточного фильтра была предложена Клаппером и Горески в 1994 году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. Позднее ими был разработан алгоритм такого шифра. Один FCSR без подключения линейного компонента не может быть использован в качестве поточного шифра, так как легко дешифруется.
В 2002 году был предложен самосинхронизующийся поточный шифр, основанный на совместном использовании FCSR и LFSRF. 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.
В 2005 году Арно и Бергер предложили идею совместного использования FCSR и линейного фильтра для создания поточного шифра, который получил название F-FCSR (Filtered FCSR)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). Позже ими были предложены 4 алгоритма, реализующих эту идею: F-FCSR-SF1, F-FCSR-SF, F-FCSR-DF1 и F-FCSR-DF8F. 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.
В 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. Но после обнаружения уязвимости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 был исключен из eSTREAM Portfolio (rev.1).
Характеристики версий Название Длина главного регистра Инициализация Фильтр Число бит на выходе фильтраF-FCSR-8 128 64/128 тактов(в зависимости от IV) Зависит от ключа 8F-FCSR-H 160 160 тактов Статический 8F-FCSR-8.2 256 258 тактов Зависит от ключа 16F-FCSR-16 256 16 + 258 тактов Статический 16F-FCSR-H v.2 160 20 + 162 такта Статический 8
Описание алгоритма
FCSR FCSR реализуется в двух конфигурациях: Галуа и Фиббоначи. В F-FCSR используется конфигурация Галуа, так как она эффективней. Вводятся следующие обозначения: q — целостность соединения (connection integer) — отрицательное нечетное целое число, удовлетворяющее следующим условиям:
T = (|q| − 1)/2 — простое, 2T — период битовой последовательности p/q Число единиц в двоичном представлении числа (1 − q)/2 порядка n/2 p — параметр, зависящий от ключа, такое, что 0 < p < |q| n — размер главного регистра FCSR, |q| в двоичной записи имеет n + 1 знаков: 2n < −q < 2n+1 d: d = (1 − q)/2, в двоичной записи , di = {0, 1}, dn-1 = 1 M — n-разрядный главный регистр, значения его i-го разряда, . C — l-разрядный регистр сдвига, l + 1 — число единиц в двоичной записи d, . (m, c) — состояние FCSR Если (m, c) — состояние FCSR в момент времени t0, , , то — двоичное представление p/q, где p = m + 2c.
Пример FCSR
q = −347, d = 174 = (10101110)2, n = 8, l = 4.
Фильтрация Фильтрующая линейная функция на выходе определяется маской () Один бит на выходе определяется следующим образом:
Инициализация С учетом слабости предыдущих версий 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)16 Последовательность битов на выходе , то есть z = (m8 + m24 + m40 + m56 + … + m136, m1 + m49 +… , … , m23 + …)
F-FCSR-16 Длина ключа 128 бит, IV — 128 бит q = −183971440845619471129869161809344131658298317655923135753017128462155618715019 Длина регистра переноса l = 130 d = (CB5E129F AD4F7E66 780CAA2E C8C9CEDB 2102F996 BAF08F39 EFB55A6E 390002C6)16 Последовательность битов на выходе
Описание атаки Первоначально найденные уязвимости 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. Тогда для возникновения (*), потребуется приблизительно последовательных нулей в бите обратной связи.
В силу предположения (*) состояния главного регистра 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 неизвестными , где :
…
Аналогично получим системы уравнений, зависящих от , где и т. д. Итого 8 систем из 20 уравнений с 20 неизвестными. Ведем следующие обозначения: , , … . Обозначим вектор Тогда системы можно записать в виде , где — известная матрица, определяемая фильтрующей функцией. Алгоритм нахождения состояния главного регистра в предположении(*) можно описать следующим образом: В момент времени t получаем на выходе байты: z(t), z(t +1), . . . , z(t + 19) for i = 0 to 7 Решаем уравнение if (нет решений) goto 1 else сохраняем возможные значения for (каждый возможный набор ) if (M из может дать на выходе z(t), z(t +1), . . . , z(t + 19)) return; goto 1 Для осуществления описанной выше атаки требуется 226 байт шифротекста. Возможно улучшение атаки, требующее 224,3 байта. Аналогичная атака может быть применена к F-FCSR-16.
Примечания
Литература 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
Категория:Потоковые шифры