Являются ли регистры сдвига с линейной обратной связью вообще нежелательными для криптологов?

10

Кац и Линделл упоминают в своей книге, что LFSR были ужасны в качестве основы для псевдослучайных генераторов, и выступают за то, чтобы они больше не использовались (ну, они также рекомендуют людям использовать блочные шифры вместо потоковых шифров). Но я вижу, например, что один из шифров в портфеле estream ( Grain , предназначенный для аппаратного обеспечения) использует LFSR, поэтому мнение о том, что LFSR не годятся, не является консенсусом.

Я хотел бы знать, много ли криптологов разделяют мнение Каца и Линделла о LFSR (и о потоковых шифрах)?

soft-question cr.crypto-security pseudorandom-generators сойка
источник
1
Я думаю, что вопрос в вашем заголовке и вопрос в теле вашего поста расходятся. Хотя я не криптолог, я бы сказал «Да» на заголовок и «Нет» на вопрос в теле сообщения. Можете ли вы улучшить свой вопрос, чтобы у него был только один гармоничный вопрос?
Тайсон Уильямс
2
Я не уверен на 100%, если это по теме для cstheory, он может быть лучше подходит для crypto.SE .
Артем Казнатчеев
@ Артем Казнатчеев: Я не знал о crypto.SE. Я считаю, что моей репутации недостаточно, чтобы перенести вопрос, но я бы не стал возражать, если бы он перенесся. (Я полагаю, что crypto.SE - это не только проблемы с реализацией)
Jay
2
@ Артем, ИМХО, вопрос в этой области. Я не специалист по криптографии, но обычно люди на практике делают много вещей, которые не имеют под собой основы, например, простые программы используются в программах в качестве генераторов псевдослучайных чисел, но на самом деле они не являются псевдослучайными и их легко предсказать. Джей, если вы хотите узнать причину, по которой Катц и Линделл говорят, что LFSR не следует использовать, то теория - правильное место для вопроса. С другой стороны, вопрос о том, есть ли консенсус, не является хорошим вопросом, ответ очевиден, то есть нет. Также вопросы опроса не являются конструктивными.
Каве
1
@ Джей, я думаю, что они не имеют в виду, что их не понимают: они не основаны на вероятных предположениях о твердости или криптографии, то есть нет веских аргументов в пользу их нерушимости. Возможно, вы захотите проверить записи лекций Чарльза Рэкоффа , я помню, что он что-то говорил по этому поводу (но я не уверен, что это в его лекциях).
Каве

Ответы:

9

Существует много типов криптоаналитических атак: линейные аппроксимации, алгебраические атаки, атаки с обменом времени, памяти и данных, атаки с ошибками .

Например, вы можете прочитать опрос: « Алгебраические атаки на потоковые шифры (опрос) »

Аннотация : Большинство потоковых шифров на основе регистров сдвига с линейной обратной связью (LFSR) уязвимы для недавних алгебраических атак. В этой обзорной статье мы описываем общие атаки: существование алгебраических уравнений и быстрые алгебраические атаки. ...

В конце вы можете найти другие соответствующие ссылки.

Еще одна хорошая статья о атаках сбоев на потоковые шифры: « Анализ сбоев потоковых шифров »

Аннотация : ... Наша цель в этой статье - разработать общие методы, которые можно использовать для атаки на стандартные конструкции потоковых шифров на основе LFSR, а также более специализированные методы, которые можно использовать против конкретных потоковых шифров, таких как RC4, LILI. -128 и SOBERt32. В то время как большинство схем могут быть успешно атакованы, мы отмечаем несколько интересных открытых проблем, таких как атака на фильтрованные конструкции FSM и анализ больших отказов Хэмминга в LFSR.

Для атак компромисса между временем и памятью вы можете прочитать: « Криптоаналитические компромиссы времени / памяти / данных для потоковых шифров ».

Марцио де Биаси
источник
1
Спасибо! Эти документы, без сомнения, будут полезны.
Джей
3

Кац и Линделл рекомендовали не использовать сами LFSR в качестве псевдослучайных генераторов. Тем не менее, возможно создать псевдослучайный генератор, используя LFSR в сочетании с другими механизмами. (В частности, PRG на основе LFSR должны включать в себя некоторый нелинейный компонент.)

user686
источник