Зерно (шифр) - Grain (cipher)

Зерно это потоковый шифр представлен в eSTREAM в 2004 г. Мартин Ад, Томас Йоханссон и Вилли Мейер. Он был выбран для окончательного портфолио eSTREAM для профиля 2 проектом eSTREAM. Зерно предназначено в первую очередь для ограниченное оборудование среды. Он принимает 80-кусочек ключ и 64-битный IV. Спецификации не рекомендуют максимальную длину вывода на пару (ключ, iv). Ряд потенциальных слабых мест в шифре был выявлен и исправлен в Зерно 128а который теперь рекомендуется использовать для аппаратных сред, обеспечивающих как 128-битную безопасность, так и аутентификацию.

Описание

160-битное внутреннее состояние зерна состоит из 80-битного регистр сдвига с линейной обратной связью (LFSR) и 80-битный регистр сдвига с нелинейной обратной связью (NLFSR). Grain обновляет один бит LFSR и один бит состояния NLFSR для каждого бита зашифрованного текста, выпущенного функцией нелинейного фильтра. 80-битный NLFSR обновляется с помощью нелинейной логической функции 5 к 1 и 1-битного линейного входа, выбранного из LFSR. Нелинейная функция 5-к-1 принимает на вход 5 битов состояния NLFSR. 80-битный LFSR обновляется линейной функцией 6: 1. Во время операций с ключом выход шифра дополнительно возвращается в виде линейных входов в функции обновления NLFSR и LFSR.

В исходной версии Grain Version 0.0 Grain один бит 80-битного NLFSR и четыре бита 80-битного LFSR подаются в нелинейную логическую функцию 5 к 1 (которая выбрана для балансировки, корреляция не зависит от первого порядка и имеет алгебраическую степень 3), и выход линейно комбинируется с 1 битом 80-битного NLFSR и выпускается как выход.

В обновленном представлении Grain Version 1.0 Grain один бит 80-битного NLFSR и четыре бита 80-битного LFSR передаются в (слегка измененную) нелинейную логическую функцию 5-к-1, а вывод линейно комбинируется с 7 битов 80-битного NLFSR и выпущены как выходные.

Для инициализации шифра 80-битный ключ загружается непосредственно в 80-битный NLFSR, а 64-битный IV загружается в младшие 64-битные LFSR, а оставшиеся 16 старших битов LFSR заполняются единицами. Шифр запечатан на 160 раундов, где 160 битов ключевой поток сгенерированные, возвращаются линейно в функции обновления LFSR и NLFSR. Во время процесса инициализации шифр не выпускает выходной поток ключей.

Авторы Grain обсуждают полную скорость распространения процесса инициализации Grain в спецификациях Grain Version 1.0: «Для инициализации с двумя разными IV, различающимися только одним битом, вероятность того, что бит регистра сдвига одинаков для обеих инициализаций, должна быть близка к 0,5. . Моделирование показывает, что это достигается после 160 часов ».

Спектакль

Шифр предназначен для параллельного выполнения до 16 раундов, что позволяет ускорить реализацию за счет большего использования оборудования.

Безопасность

Размер ключа составляет 80 бит, а размер IV определен как 64 бита. Авторы утверждают, что шифр спроектирован таким образом, что никакая атака быстрее, чем исчерпывающий поиск ключа, не должна быть возможна, следовательно, лучшая атака должна требовать вычислительной сложности не значительно ниже 2⁸⁰.

В исходных спецификациях Grain Version 0.0,^[1] авторы утверждают: «Grain обеспечивает более высокую безопасность, чем несколько других хорошо известных шифров, предназначенных для использования в аппаратных приложениях. Хорошо известными примерами таких шифров являются E0 используется в Bluetooth и A5 / 1 используется в GSM. Эти шифры, хотя и имеют очень небольшую аппаратную реализацию, оказались очень небезопасными. В сравнении с E0 и A5 / 1, Grain обеспечивает более высокий уровень безопасности при сохранении небольшой аппаратной сложности ».

Авторы цитируют нападение на E0 ^[2] требуется сложность 2⁴⁰ и 2³⁵ фреймы (длина фрейма 2745 бит). Оригинальный шифр Grain Version 0.0 был взломан атакой восстановления ключа^[3] что потребовало сложности 2⁴³ вычислений и 2³⁸ биты ключевого потока для определения 80-битного ключа.

В пересмотренных спецификациях Grain Version 1.0,^[4] в шифре немного изменена функция вывода, а функция обратной связи NLFSR претерпела незначительные изменения. В спецификациях утверждается: «Функция фильтрации довольно мала, всего 5 переменных и нелинейность 12. Однако это частично компенсируется тем фактом, что один из входов берется из NLFSR. Входной бит из NLFSR будет зависеть нелинейно [sic ] на других битах в состоянии, как из LFSR, так и из NLFSR. Функция малого фильтра также компенсируется линейным добавлением 7 бит [sic ] из NLFSR в подходящих местах для формирования выходной функции ".

По состоянию на октябрь 2006 г. не известно ни одной атаки восстановления ключа лучше, чем атака грубой силы против Grain Version 1.0.

Однако атака с использованием связанных ключей была опубликована в сентябре 2006 года Озгулом Кучуком в статье «Атака с повторной синхронизацией слайдов при инициализации Grain 1.0».^[5] В документе утверждается: «мы находим связанные ключи и начальные значения потокового шифра Grain 1.0. Для любой пары (K, IV) существует связанная пара (K ', IV') с вероятностью 1/22, которая генерирует сдвинутый на 1 бит поток ключей. . Хотя это еще не приводит к эффективной атаке восстановления ключа, это указывает на слабость в инициализации, которую можно было бы преодолеть [sic ] с небольшим усилием ".

Рекомендации

1. Мартин Ад, Томас Йоханссон, Вилли Мейер (2005-04-29). «Grain - потоковый шифр для сред с ограничениями» (PDF ). eSTREAM.
2. Йи Лу, http://lasecwww.epfl.ch/~vaudenay/ (2004). «Криптоанализ двухуровневого генератора ключевого потока Bluetooth E0» (PDF ). Достижения в криптологии - Asiacrypt 2004, LNCS vol. 3329, стр 483-499, Springer, 2004.
3. Ком Бербен, Анри Жильбер, Александр Максимов (02.01.2006). «Криптоанализ зерна» (PDF ). eSTREAM.
4. Мартин Ад, Томас Йоханссон, Вилли Мейер (2006). «Grain - потоковый шифр для сред с ограничениями» (PDF ). eSTREAM.
5. Озгуль Кучук (2006-07-16). "Атака повторной синхронизации слайдов при инициализации зерна 1.0" (PS ). eSTREAM.

внешняя ссылка

• Страница eSTREAM на сайте Grain