Зерно (шифр)
Grain — поточный шифр, представленный на eSTREAM в 2004 году Мартином Хеллом , Томасом Йоханссоном и Вилли Мейером . Он был выбран для окончательного портфеля eSTREAM для профиля 2 проектом eSTREAM. Grain предназначен в первую очередь для ограниченных аппаратных сред. Он принимает 80- битный ключ и 64-битный IV . В спецификациях не рекомендуется максимальная длина вывода для пары (ключ, iv). Ряд потенциальных уязвимостей в шифре был выявлен и исправлен в Grain 128a , который теперь рекомендуется использовать в аппаратных средах, обеспечивающих как 128-битную безопасность, так и аутентификацию.
Описание [ править ]
160-битное внутреннее состояние Grain состоит из 80-битного регистра сдвига с линейной обратной связью (LFSR) и 80-битного регистра сдвига с нелинейной обратной связью (NLFSR). Зерно обновляет один бит состояния LFSR и один бит состояния NLFSR для каждого бита зашифрованного текста, выпущенного функцией нелинейного фильтра. 80-битный NLFSR обновляется с помощью нелинейной логической функции 5-к-1 и 1-битного линейного входа, выбранного из LFSR. Нелинейная функция 5-к-1 принимает на вход 5 бит состояния NLFSR. 80-битный LFSR обновляется с помощью линейной функции 6 к 1. Во время операций шифрования выходные данные шифра дополнительно передаются обратно в виде линейных входов в функции обновления NLFSR и LFSR.
В исходной версии Grain версии 0.0 один бит 80-битного NLFSR и четыре бита 80-битного LFSR передаются в нелинейную логическую функцию 5-к-1 (которая выбрана как сбалансированная, невосприимчивая к корреляциям). первого порядка и имеет алгебраическую степень 3), а выходные данные линейно комбинируются с 1 битом 80-битного NLFSR и выдаются как выходные данные.
В обновленной версии Grain версии 1.0 один бит 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 версии 1.0: «Для инициализации с двумя разными IV, отличающимися только на один бит, вероятность того, что бит сдвигового регистра будет одинаковым для обеих инициализаций, должна быть близка к 0,5. Моделирование показывает, что это достигается после 160 тактов».
Производительность [ править ]
Шифр спроектирован так, чтобы обеспечить параллельное выполнение до 16 раундов, что позволяет ускорить реализацию за счет большего использования оборудования.
Безопасность [ править ]
Размер ключа составляет 80 бит, а размер IV указан как 64 бита. Авторы утверждают, что шифр спроектирован таким образом, что невозможна атака быстрее, чем полный поиск ключей, поэтому лучшая атака должна требовать вычислительной сложности не значительно ниже 2. 80 .
В исходных спецификациях Grain версии 0.0 [1] авторы утверждают: «Grain обеспечивает более высокий уровень безопасности, чем некоторые другие хорошо известные шифры, предназначенные для использования в аппаратных приложениях. Хорошо известными примерами таких шифров являются E0, используемый в Bluetooth , и A5/1, используемый в GSM . Эти шифры, хотя и имеют очень маленькая аппаратная реализация оказалась очень небезопасной. По сравнению с E0 и A5/1 , Grain обеспечивает более высокий уровень безопасности, сохраняя при этом небольшую сложность оборудования».
Авторы цитируют атаку на E0 [2] требуется сложность 2 40 и 2 35 кадры (длина кадра составляет 2745 бит). Оригинальный шифр Grain версии 0.0 был взломан в результате атаки с восстановлением ключа. [3] что требовало сложности 2 43 расчеты и 2 38 биты потока ключей для определения 80-битного ключа.
В пересмотренных спецификациях Grain версии 1.0: [4] шифр имеет немного измененную функцию вывода, а функция обратной связи NLFSR претерпела незначительные изменения. В спецификациях утверждается: «Функция фильтра довольно маленькая, всего 5 переменных и нелинейность 12. Однако отчасти это компенсируется тем, что один из входов берется из NLFSR. Входной бит от NLFSR будет зависеть нелинейно [ sic ] на других битах состояния, как из LFSR, так и из NLFSR. Небольшая функция фильтра также компенсируется путем линейного добавления 7 битов [ sic ] из NLFSR в подходящих позициях для формирования выходной функции».
По состоянию на октябрь 2006 года не известно никаких атак с восстановлением ключей, которые были бы лучше, чем атака методом перебора, против Grain версии 1.0.
Однако атака с использованием связанного ключа была опубликована в сентябре 2006 года Озгулем Кучуком в статье «Атака ресинхронизации слайдов при инициализации Grain 1.0». [5] В документе утверждается: «мы находим связанные ключи и начальные значения потокового шифра Grain 1.0. Для любой пары (K,IV) существует связанная пара (K',IV') с вероятностью 1/22, которая генерирует 1-битный сдвинутый поток ключей. Хотя это пока не приводит к эффективной атаке по восстановлению ключа, это указывает на слабость инициализации, которую можно преодолеть [ sic ] приложив небольшие усилия».
Ссылки [ править ]
- ^ Мартин Хелл , Томас Йоханссон , Вилли Мейер (29 апреля 2005 г.). «Зерно — поточный шифр для ограниченных сред» (PDF) . еСТРИМ.
{{cite web}}: CS1 maint: несколько имен: список авторов ( ссылка ) - ^ Йи Лу , http://lasecwww.epfl.ch/~vaudenay/ (2004). «Криптоанализ двухуровневого генератора ключевых потоков Bluetooth E0» (PDF) . Достижения в криптологии – Asiacrypt 2004, LNCS vol. 3329, стр. 483–499, Спрингер, 2004 г.
- ^ Ком Бербен , Анри Жильбер , Александр Максимов (2 января 2006 г.). «Криптоанализ зерна» (PDF) . еСТРИМ. Архивировано из оригинала (PDF) 11 октября 2006 г. Проверено 26 февраля 2006 г.
{{cite web}}: CS1 maint: несколько имен: список авторов ( ссылка ) - ^ Мартин Хелл , Томас Йоханссон , Вилли Мейер (2006). «Зерно — поточный шифр для ограниченных сред» (PDF) . еСТРИМ.
{{cite web}}: CS1 maint: несколько имен: список авторов ( ссылка ) - ^ Озгуль Кучук (16 июля 2006 г.). «Атака ресинхронизацией слайдов на инициализацию Grain 1.0» . еСТРИМ. Архивировано из оригинала ( PS ) 27 мая 2011 г. Проверено 10 октября 2006 г.
Внешние ссылки [ править ]
- Страница eSTREAM о зерне. Архивировано 6 октября 2008 г. в Wayback Machine.
| |||||||||||||||||||||
