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 реализуется в двух конфигурациях: Галуа и Фиббоначи. В F-FCSR используется конфигурация Галуа, так как она эффективней. Вводятся следующие обозначения:
Если (m, c) — состояние FCSR в момент времени t0, , , то — двоичное представление p/q, где p = m + 2c.
q = −347, d = 174 = (10101110)2, n = 8, l = 4.
Фильтрующая линейная функция на выходе определяется маской ( ) Один бит на выходе определяется следующим образом:
С учетом слабости предыдущих версий F-FCSR из-за слабого начального перемешивания битов в главном регистре процедура инициализации в F-FCSR-H v.2 и F-FCSR-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 неизвестными.
Ведем следующие обозначения:
,
,
…
.
Обозначим
вектор
Тогда системы сожно записать в виде
, где
— известная матрица, определяемая фильтрующей функцией.
Алгоритм нахождения состояния главного регистра в предположении(*) можно описать следующим образом:
Для осуществления описанной выше атаки требуется 226 байт шифротекста. Возможно улучшение атаки, требуюшее 224,3 байта. Аналогичная атака может быть применена к F-FCSR-16.
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .